题意：
求第n个不为完全平方数倍数的数
题解：
网上有人说答案不会超过2n （求证0 0？） 竟然不超过2n 那么很明显就是用二分做了
二分判定就是要求小于等于n的合法的数的个数
不难发现一个数若为完全平方数的倍数 则他的质因子肯定有一个的指数大于1
那么合法的数的所有质因数质数肯定都为1
_________________________________________________________________________________
于是题目变为 求小于等于的质因数指数都为1的数的个数
我们可以把<=n的 所有i^2的倍数的数减掉(i为质数)
算重？
莫比乌斯函数！（容斥原理- -）
答案就是n-奇数个质数的平方的倍数的个数+偶数个质数的平方的倍数的个数
即 ans=Σmiu[i]*(n/i^2) （i<=(int) sqrt(n) 显然i如果>sqrt(n)个数肯定为0）
1 (i为奇数个质数的乘积)
miu[i]= -1 (i为偶数个质数的乘积)
0 (i有某个质数指数>1)
_________________________________________________________________________________
代码：
#include <cstdio>
#include <cmath>
typedef long long ll;
const ll M=;
ll t,n,miu[M],pri[M],bo[M],ans;
void makemiu(){
miu[]=;
for (ll i=;i<M;i++){
if (!bo[i]){
pri[++pri[]]=i;
miu[i]=-;
}
for (ll j=;j<=pri[] && pri[j]*i<M;j++){
bo[i*pri[j]]=;
if (i%pri[j]==){
miu[i*pri[j]]=;
break;
}else miu[i*pri[j]]=-miu[i];
}
}
}
ll check(ll t){
ll sq=(int)sqrt(t),res=;
for (ll i=;i<=sq;i++)
res=res+miu[i]*(t/(i*i));
return res;
}
ll getans(ll t){
ll l=,r=t*,mid;
while (l+<r){
mid=(l+r)/;
if (check(mid)<t) l=mid;
else r=mid;
}
return r;
}
int main(){
scanf("%I64d",&t);
makemiu();
for (ll i=;i<=t;i++){
scanf("%I64d",&n);
printf("%I64d\n",getans(n));
}
}