#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5;
int pr,p[N],mu[N];
bool v[N];
void init()
{
	memset(v,0,sizeof v);
	memset(mu,0,sizeof mu);
	for(int i=2;i<N;i++)
	{
		if(!v[i])p[++pr]=i,mu[i]=-1;
		for(int j=1;j<=pr&&i*p[j]<N;j++)
		{
			v[i*p[j]]=1;
			if(i%p[j]==0)break;
			mu[i*p[j]]=-mu[i];
		}
	}
}
int calc(int x)
{
	int res=x;
	for(int i=2;i*i<=x;i++)
		res+=mu[i]*(x/(i*i));
	return res;
}
void solve()
{
	int k;scanf("%lld",&k);
	int l=k,r=1e10,mid,ans=0;
	while(l<=r)
	{
		mid=(l+r)>>1;
		int sum=calc(mid);
		if(sum<k)l=mid+1;
		else r=mid-1,ans=mid;
	}
	printf("%lld\n",ans);
}
signed main()
{
	init();
	int T;scanf("%lld",&T);
	while(T--)solve();
	return 0;
}

阎帝的代码，init()函数类似于线性筛素数，可以借鉴一下。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1e5;
int pr,p[N+10];int mu[N+10];bool v[N+10];
void init()
{
	memset(v,0,sizeof(v));
	pr=0;
	for(int i=2;i<=N;i++)
	{
		if(!v[i])p[++pr]=i,mu[i]=-1;//找到了质数,标记一下
		for(int j=1;j<=pr&&i*p[j]<=N;j++)
		{
			v[i*p[j]]=1;
			if(i%p[j]==0){mu[i*p[j]]=0;break;}//计算过,不用再算 
			mu[i*p[j]]=-mu[i];//容斥原理,这个数前的系数和ta的前任互为相反数
		}
	}
}
LL calc(LL x)//1~x中符合要求的数 
{
	LL res=x;//从所有的往下减 
	for(LL i=2/*除了1*/;i*i<=x;i++)res+=mu[i]*(x/(i*i));
	return res;
}
/*
calc()函数
开始为x个，然后：
减去 2^2的倍数的个数
减去 3^2的倍数的个数
不减 4^2的倍数的个数
减去 5^2的倍数的个数
加上 6^2的倍数的个数（因为被 2 和 3 总共减去了2次，减重复了）。 
……
容斥！莫比乌斯函数的专业领域 
*/
int main()
{
	init();
	int T;scanf("%d",&T);
	while(T--)
	{
		LL k;scanf("%lld",&k);
		LL l=k,r=1e10,ans=0;//二分找答案
		while(l<=r)
		{
			LL mid=(l+r)>>1;
			if(calc(mid)>=k)r=mid-1,ans=mid;
			else l=mid+1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

G12 筛法求莫比乌斯函数

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5;
int pr, p[N+10];LL mu[N+10]; bool v[N+10];
void init()
{
	memset(v,0,sizeof(v));
	pr=0;mu[0]=0;mu[1]=1;
    for(int i=2;i<=N;i++)
	{
        if(!v[i]) p[++pr]=i,mu[i]=-1; 
        for(int j=1;j<=pr&&p[j]*i<=N;j++)
		{
            v[i*p[j]]=true;
            if(i%p[j]==0){mu[i*p[j]]=0;break;}
            mu[i*p[j]]=-mu[i];
        }
    }
}
/*calc(LL x)函数功能：统计 1~x 好的数有多少个？
开始为x个，然后：
减去 2^2的倍数的个数
减去 3^2的倍数的个数
不减 4^2的倍数的个数
减去 5^2的倍数的个数
加上 6^2的倍数的个数（因为被 2 和 3 总共减去了2次，减重复了）。 
……
容斥！莫比乌斯函数的专业领域 
*/ 
LL calc(LL x)  
{
	LL res=x; 
	for(LL i=2;i*i<=x;i++) res+=mu[i]*(x/(i*i));
    return res;
}
int main()
{
	init();
	int T;scanf("%d", &T);
	while(T--)
	{
        LL K;scanf("%lld", &K);
		LL l=K, r=LL(1e10), ans=0; 
		while(l<=r)
		{
			LL mid=(l+r)>>1;
			if(calc(mid)>=K) r=mid-1, ans=mid;
			else l=mid+1;
		}
		printf("%lld\n", ans);
	}
    return 0;
}