BZOJ 2440 完全平方数（莫比乌斯反演+二分查找）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23362

题意：定义含有平方数因子的数为完全平方数（平方数因子不包含1）。求第k个非完全平方数。

思路：我们先求出[1, n]的非完全平方数的个数，然后利用二分来查找正好等于k时的n（注意这样的n可能不止一个，求最左边的）。关键是，怎么求出前者，我们可以利用容斥原理，用n - [1, n]内完全平方数的个数，求[1, n]内完全平方数的个数，用容斥发现前面的系数就是莫比乌斯函数，直接用莫比乌斯反演即可，结果为sigma(mu[i]*(n/(i*i)))。

code：

 #include <cstdio>

 #include <cstring>

 using namespace std;

 typedef long long LL;

 const LL INF = 2e10 + ;

 const int MAXN = ;

 bool check[MAXN];

 int primes[MAXN];

 int mu[MAXN];

 LL k;

 void moblus()

 {

     memset(check, false, sizeof(check));

     mu[] = ;

     int cnt = ;

     for (int i = ; i < MAXN; ++i) {

         if (!check[i]) {

             primes[cnt++] = i;

             mu[i] = -;

         }

         for (int j = ; j < cnt; ++j) {

             if (i * primes[j] > MAXN) break;

             check[i * primes[j]] = true;

             if (i % primes[j] == ) {

                 mu[i * primes[j]] = ;

                 break;

             } else {

                 mu[i * primes[j]] = -mu[i];

             }

         }

     }

 }

 LL cal(LL n)

 {

     LL ret = n;

     for (LL i = ; i * i <= n; ++i) {

         ret += mu[i] * (n / (i * i));

     }

     return ret;

 }

 int main()

 {

     moblus();

     int nCase;

     scanf("%d", &nCase);

     while (nCase--) {

         scanf("%lld", &k);

         LL lhs = 1L;

         LL rhs = INF;

         LL mid;

         while (lhs < rhs) {

             mid = (rhs + lhs) / ;

             LL tmp = cal(mid);

             if (tmp < k) lhs = mid + ;

             else rhs = mid;

         }

         printf("%lld\n", lhs);

     }

     return ;

 }