BZOJ 2440 中山市选 2011 完全平方数 莫比乌斯函数+二分

题目大意

给出一个数k，，求第k个不是完全平方数个数的数字（这里的完全平方数并不包括1）。

思路

首先介绍一下莫比乌斯函数(Mbius):

然后呢，由于莫比乌斯函数是个积性函数，于是我们就可以线性地求出所有需要的莫比乌斯函数值。 剩下的工作就是在外层套一个二分，转成判定问题，小于一个数的数字中有多少个数字不是完全平方数的倍数。这个东西用容斥乱搞一下就好了~

CODE;int mu[MAX], prime[MAX], primes;bool notp[MAX];void Shaker(){mu[1] = 1;for(int i = 2; i < MAX; ++i) {if(!notp[i])mu[i] = -1, prime[++primes] = i;for(int j = 1; prime[j] * i < MAX && j <= primes; ++j) {notp[prime[j] * i] = true;if(i % prime[j] == 0) {mu[prime[j] * i] = 0;break;}mu[prime[j] * i] -= mu[i];}}}int asks, k;inline int Judge(int x){int re = 0;for(int i = 1; i * i <= x; ++i)re += x / (i * i) * mu[i];return re;}inline int Work(int x){int l = 1, r = x << 1, ans = 1;while(l <= r) {int mid = (l >> 1) + (r >> 1) + (l&r&1);if(Judge(mid) >= x)r = mid – 1, ans = mid;elsel = mid + 1;}return ans;}int main(){Shaker();for(cin >> asks; asks–;) {scanf(“%d”, &k);printf(“%d\n”, Work(k));}return 0;}

先知三日，富贵十年。