题解,求关注

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e6+10;
int mu[maxn],prime[maxn],tot,T,n;
bool used[maxn];
void euler_sieve()
{
    mu[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!used[i]) { prime[++tot]=i; mu[i]=-1; }
        for(int j=1;j<=tot and prime[j]*i<maxn;j++)
        {
            used[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            else
                mu[i*prime[j]]=-mu[i];
        }
    }
}
long long find(long long x)
{
    long long ans=0;
    for(int i=1;1ll*i*i<=x;i++)
        ans+=mu[i]*(x/(i*i));
    return ans;
}
void solve(long long x)
{
    long long l=1,r=x<<1,ans=0,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(find(mid)<x)l=mid+1;
        else ans=mid,r=mid-1;
    }
    cout<<ans<<endl;
} 
int main()
{
        euler_sieve();
        cin>>T;
        while(T--)
        {
            cin>>n;
            solve(n);
        }
        return 0;
}