首先根据样例或者自己打表大概可以知道，对于询问k，答案不会超过k<<1，那么我们就可以二分答案，求当前二分的值内有多少个数不是完全平方数的倍数，这样就可以了，对于每个二分到的值x，其中完全平方数的倍数的个数为Σmiu(i)*(n/(i*i))，原理就是容斥，但是根据莫比乌斯反演应该也是能推出来的（我没推出来）。
反思：开始莫比乌斯函数筛错了，后来的时候没用longlong，导致二分的时候int溢出了，这样就死循环了，找了半天错。
/************************************************************** Problem: 2440 User: BLADEVIL Language: C++ Result: Accepted Time:1164 ms Memory:2456 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #include <iostream> #include <cmath> #define maxn 50010 using namespace std; long long mindiv[maxn],prim[maxn],miu[maxn]; void prepare() { miu[1]=1; for (long long i=2;i<=50000;i++) { if (!mindiv[i]) { prim[++prim[0]]=i; miu[i]=-1; } for (long long j=1;j<=prim[0]&&prim[j]*i<=50000;j++) { mindiv[i*prim[j]]=prim[j]; if (!(i%prim[j])) { miu[i*prim[j]]=0; break; } miu[i*prim[j]]=-miu[i]; } } } long long calc(long long x) { long long tot=0,t; for (long long i=1;i<=sqrt(x);i=t+1) { t=x/(x/(i*i)); t=sqrt(t); //printf("%d %d ",i,t); tot+=(miu[t]-miu[i-1])*(x/(i*i)); //printf("%d ",tot); //printf("%d %d ",miu[t],miu[i-1]); } return tot; } int main() { prepare(); for (long long i=1;i<=50000;i++) miu[i]+=miu[i-1]; //printf("%d",calc(1)); //for (long long i=1;i<=100;i++) printf("%d ",miu[i]); long long task; scanf("%lld",&task); while (task--) { long long l=1ll,r,n,ans; scanf("%lld",&n); r=n<<1; while (l<=r) { long long mid=(l+r)>>1; //printf("%d %d %d ",l,r,mid); if (calc(mid)>=n) { ans=mid; r=mid-1ll; } else l=mid+1ll; //printf("%d %d %d ",l,r,mid); } printf("%lld ",ans); } return 0; }