题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2440
从PoPoQQQ大佬的ppt里看到这个题，附链接：
https://wenku.baidu.com/view/fbec9c63ba1aa8114431d9ac.html
代码：
#include<bits/stdc++.h> using namespace std; const int MAXN=1000000; typedef long long ll; bool check[MAXN+10]; int prime[MAXN+10]; int mu[MAXN+10]; void Moblus() { memset(check,false,sizeof(check)); mu[1]=1; int tot=0; for(int i=2;i<=MAXN;i++) { if(!check[i]) { prime[tot++]=i; mu[i]=-1; } for(int j=0;j<tot;j++) { if(i*prime[j]>MAXN) break; check[i*prime[j]]=true; if(i%prime[j]==0) { mu[i*prime[j]]=0; break; } else { mu[i*prime[j]]=-mu[i]; } } } } ll solve(ll n) { ll ans=0; for(ll i=1;i*i<=n;i++) { ans+=mu[i]*(n/(i*i)); } return ans; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); Moblus(); int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); ll l=1,r=2e9,ans; while(l<=r) { ll mid=(l+r)>>1; ll cnt=solve(mid); if(cnt>=n) { r=mid-1; ans=mid; } else { l=mid+1; } } printf("%lld\n",ans); } return 0; }