题目链接：

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

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

code：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 typedef long long LL; 6  7 const LL INF = 2e10 + 7; 8 const int MAXN = 100005; 9 10 bool check[MAXN];11 int primes[MAXN];12 int mu[MAXN];13 LL k;14 15 void moblus()16 {17     memset(check, false, sizeof(check));18     mu[1] = 1;19     int cnt = 0;20     for (int i = 2; i < MAXN; ++i) {21         if (!check[i]) {22             primes[cnt++] = i;23             mu[i] = -1;24         }25         for (int j = 0; j < cnt; ++j) {26             if (i * primes[j] > MAXN) break;27             check[i * primes[j]] = true;28             if (i % primes[j] == 0) {29                 mu[i * primes[j]] = 0;30                 break;31             } else {32                 mu[i * primes[j]] = -mu[i];33             }34         }35     }36 }37 38 LL cal(LL n)39 {40     LL ret = n;41     for (LL i = 2; i * i <= n; ++i) {42         ret += mu[i] * (n / (i * i));43     }44     return ret;45 }46 47 int main()48 {49     moblus();50     int nCase;51     scanf("%d", &nCase);52     while (nCase--) {53         scanf("%lld", &k);54         LL lhs = 1L;55         LL rhs = INF;56         LL mid;57         while (lhs < rhs) {58             mid = (rhs + lhs) / 2;59             LL tmp = cal(mid);60             if (tmp < k) lhs = mid + 1;61             else rhs = mid;62         }63         printf("%lld\n", lhs);64     }65     return 0;66 }