题意：找到第k个无平方因子数。
解法：这道题非常巧妙的运用了莫比乌斯函数的性质！
解法参考https://www.cnblogs.com/enzymii/p/8421314.html这位大佬的。这里我说下自己的理解：
首先看到K这么大，想到可能要二分答案。那么我们二分答案M，问题就变成计算<=M的数有多少个无平方因子数。
我们考虑这样一个算法：枚举<=M的每一个无平方因子数，然后枚举它的倍数将其去掉。但是这个方法有一个问题就是会重复删除，例如一个数 2*3*5 ，他会被2/3/5分别删除一次，然后又会被2*3/2*5/3*5删除(等等)......处理这种重复问题我们一般会采用容斥原理。
于是我们想办法 -一个因子倍数+两个因子倍数-三个因子倍数....... ； 想上诉的2*3*5， -（2/3/5）+（2*3/2*5/3*5）-（2*3*5）= -1 。这样我们就解决了重复问题！！！
那么再仔细观察这个系数，奇数个质因子的无平方数系数是-1，偶数个质因子的无平方数的系数是1，这不就是莫比乌斯函数！！！
于是我们得到了式子：
于是此题可解了：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int N=1e5+10; 5 const int Pr=1e5; 6 int K; 7 8 bool vis[N]; 9 int tot=0,pri[N]; LL mu[N]; 10 void prework() { 11 vis[1]=1; mu[1]=1; 12 for (int i=2;i<=Pr;i++) { 13 if (!vis[i]) pri[++tot]=i,mu[i]=-1; 14 for (int j=1;j<=tot&&i*pri[j]<=Pr;j++) { 15 int k=i*pri[j]; vis[k]=1; 16 if (i%pri[j]==0) { 17 mu[k]=0; break; 18 } 19 mu[k]=-mu[i]; 20 } 21 } 22 } 23 24 bool check(LL M) { 25 LL i=1,j,ret=0; 26 for (int i=1;i*i<=M;i++) ret+=mu[i]*(M/(i*i)); 27 return ret>=K; 28 } 29 30 int main() 31 { 32 prework(); 33 int T; cin>>T; 34 while (T--) { 35 scanf("%d",&K); 36 LL L=1,R=2*K; 37 while (L<R) { 38 LL M=(L+R)/2; 39 if (check(M)) R=M; else L=M+1; 40 } 41 printf("%lld\n",R); 42 } 43 return 0; 44 }
BZOJ2440/洛谷P4318 [中山市选2011]完全平方数 莫比乌斯函数
原文：https://www.cnblogs.com/clno1/p/11644686.html