题意：第Ki 个不是完全平方数的正整数倍的数。
对于一个数t，t以内的数里的非完全平方数倍数的个数：num=1的倍数的数量−一个质数平方数(9,25,49...)的倍数的数量+两个质数的积平方数(36,100,225...)的数量−三个质数balabala……
所以 (然而这一坨是怎么推出来的呢？)
u(i)就是莫比乌斯函数
求莫比乌斯函数代码：
//递推
ll mu[100005];
void mobius(ll mn)
{
mu[1]=1;
for(ll i=1;i<=mn;i++){
for(ll j=i+i;j<=mn;j+=i){
mu[j]-=mu[i];
}
}
}
//main
mobius(100000);//线性筛法求莫比乌斯函数
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];
}
}
}
}
所以代码：
#include <cstdio>
#include <cmath>
typedef long long ll;
const ll M=100001;
ll t,n,miu[M],pri[M],bo[M],ans;
void makemiu(){
miu[1]=1;
for (ll i=2;i<M;i++){
if (!bo[i]){
pri[++pri[0]]=i;
miu[i]=-1;
}
for (ll j=1;j<=pri[0] && pri[j]*i<M;j++){
bo[i*pri[j]]=1;
if (i%pri[j]==0){
miu[i*pri[j]]=0;
break;
}else miu[i*pri[j]]=-miu[i];
}
}
}
ll check(ll t){
ll sq=(int)sqrt(t),res=0;
for (ll i=1;i<=sq;i++)
res=res+miu[i]*(t/(i*i));
return res;
}
ll getans(ll t){
ll l=0,r=t*2,mid;
while (l+1<r){
mid=(l+r)/2;
if (check(mid)<t) l=mid;
else r=mid;
}
return r;
}
int main(){
scanf("%I64d",&t);
makemiu();
for (ll i=1;i<=t;i++){
scanf("%I64d",&n);
printf("%I64d\n",getans(n));
}
}