先二分一下变成判定性问题。
在 (1 ldots n) 内，所有的没有平方因子的数的个数是：
[n - frac{n}{2^2} - frac{n}{3^2} - cdots + frac{n}{(2 imes 3)^2} + cdots
]
惊奇地发现也就是
[sum_{k=1}^{sqrt{n}}mu(k)left lfloor frac{n}{k^2}
ight
floor
]
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
int T, mu[100005], pri[100005], cnt;
bool isp[100005];
ll k;
void shai(){
memset(isp, true, sizeof(isp));
isp[0] = isp[1] = false;
mu[1] = 1;
for(int i=2; i<=100000; i++){
if(isp[i]) pri[++cnt] = i, mu[i] = -1;
for(int j=1; j<=cnt; j++){
if(i*pri[j]>100000) break;
isp[i*pri[j]] = false;
if(i%pri[j]==0){
mu[i*pri[j]] = 0;
break;
}
else mu[i*pri[j]] = -mu[i];
}
}
}
ll chk(int x){
ll q=sqrt(x), re=0;
for(int i=1; i<=q; i++)
re += mu[i] * x / (i * i);
return re;
}
int main(){
cin>>T;
shai();
while(T--){
scanf("%lld", &k);
ll l=1, r=2e9, mid, ans;
while(l<=r){
mid = (l + r) >> 1;
if(chk(mid)>=k){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
printf("%lld
", ans);
}
return 0;
}