题目大意：求第k个无平方因子数 这道题需要先进行二分答案，[1…x]内的无平方因子的数。 然后根据容斥原理可得，ans=0个质数之积的平方的倍数个数-1个质数之积的平方的倍数个数+2个质数之积的平方的倍数个数…. 然后可以得到对于每一个数i，它前面的系数正好等于它的莫比乌斯函数值。
ans=∑i=1⌊n√⌋μ(i)⌊ni2⌋
其实此题与莫比乌斯反演没有关系，只是一个莫比乌斯函数的应用而已。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define MAXN 100005 using namespace std; int n; long long miu[MAXN],prime[MAXN]; void work() { miu[1]=1; int cnt=0; bool check[MAXN]; memset(check,0,sizeof check); for(int i=2;i<=MAXN;i++) { if(!check[i]) { miu[i]=-1; prime[++cnt]=i; } for(int j=1;j<=cnt;j++) { if(i*prime[j]>MAXN) break; check[i*prime[j]]=1; if(i%prime[j]==0) { miu[i*prime[j]]=0; break; } miu[i*prime[j]]=miu[i]*miu[prime[j]]; } } } long long num(int x) { long long ans=0; for(int i=1;i<=sqrt(x);i++) { ans+=miu[i]*(x/(i*i)); } return ans; } long long work(int x) { long long l=0,r=x*2; while(r-l>1) { long long mid=(l+r)/2; if(num(mid)<x) l=mid; else r=mid; } return r; } int main() { work(); int T; scanf("%d",&T); while(T--) { scanf("%d",&n); printf("%lld\n",work(n)); } }