POJ 2773 Happy 2006 (公式法 or 二分容斥定理)

http://poj.org/problem id=2773

首先看一个简单的方法：

若K<=phi(n)，直接暴力计算即可；

若K>phi(n)，我们可以利用gcd(k'+λn,n)=gcd(k',n)，将其转化为K<=phi(n)的情况，

具体代码如下：

/*2355ms,3504KB*/

#include 
  
   
const int maxn = 1000005;

int num[maxn];

int gcd(int a, int b) {return b   gcd(b, a % b) : a;}

int main()
{
	int n, k;
	while (~scanf("%d%d", &n, &k))
	{
		int cnt = 0;
		for (int i = 1; i <= n; i++)
			if (gcd(n, i) == 1) num[++cnt] = i;
		int t = k % cnt, p = k / cnt;
		if (t == 0) t = cnt, p--;
		printf("%d\n", num[t] + n * p);
	}
	return 0;
}

  

但是这个方法太慢了，更快的方法如下：

首先处理出n的质因子集合{p1,p2,p3,...}

然后从另一个角度看K：

对于一个数num，若将其p1的倍数划去，p2的倍数划去，p3的倍数划去，…，最后若恰好剩下K个数，这个num就是我们要找的数。

我们可以二分找num，但要注意的是，可能有两个不同的num，它们在划去pi后都剩下K个数，这时我们要取小的那个数。

而计算剩下的数的个数，可以用容斥定理搞定。

完整代码：

/*0ms,372KB*/

#include
  
   
const int mx = 1005;
const int MAX = 1000000000;

bool vis[mx];
int prime[mx], a[11], cnt, cnt_n;

void init()
{
	for (int i = 2 ; i < mx; i++)
		if (!vis[i])
		{
			prime[cnt++] = i;
			for (int j = i * i ; j < mx; j += i)
				vis[j] = true;
		}
}

/// O(log n)求n的所有质因子,不超过10个
void getprime(int n)
{
	cnt_n = 0;
	for (int i = 0; i < cnt && prime[i] * prime[i] <= n; i++)
		if (n % prime[i] == 0)
		{
			a[cnt_n++] = prime[i];
			while (n % prime[i] == 0)
				n /= prime[i];
		}
	if (n > 1) a[cnt_n++] = n;
}

/// 计算划去pi的倍数后剩下的数的个数
int left(int num)
{
	int sum = 0;///划去的数的个数
	for (int i = 1; i < (1 << cnt_n); i++) /// 注意cnt_n的个数与log n差不多(一般不超过10)，所以可以用位运算
	{
		int tmp = 1, one = 0;
		for (int j = 0; j < cnt_n; j++)
			if ((1 << j) & i)
			{
				one++;///i的二进制中1的个数
				tmp *= a[j];
			}
		if (one & 1) sum += num / tmp;
		else sum -= num / tmp;
	}
	return num - sum;
}

int main()
{
	init();
	int n, K;
	while (~scanf("%d%d", &n, &K))
	{
		getprime(n);
		int l = 1, r = MAX, mid, ans;
		while (l <= r)
		{
			mid = (l + r) >> 1;
			int pt = left(mid);
			if (pt >= K)
			{
				if (pt == K) ans = mid; /// 但这可能不是真正的答案，还要看看有没有更小的数也满足条件
				r = mid - 1;
			}
			else l = mid + 1;
		}
		printf("%d\n", ans);
	}
	return 0;
}