bzoj 2440 容斥原理

/**************************************************************
    Problem: 2440
    User: BLADEVIL
    Language: C++
    Result: Accepted
    Time:1164 ms
    Memory:2456 kb
****************************************************************/
 
//By BLADEVIL
#include <cstdio>
#include <iostream>
#include <cmath>
#define maxn 50010
 
using namespace std;
 
long long mindiv[maxn],prim[maxn],miu[maxn];
 
void prepare()
{
    miu[1]=1;
    for (long long i=2;i<=50000;i++)
    {
        if (!mindiv[i])
        {
            prim[++prim[0]]=i;
            miu[i]=-1;
        }
        for (long long j=1;j<=prim[0]&&prim[j]*i<=50000;j++)
        {
            mindiv[i*prim[j]]=prim[j];
            if (!(i%prim[j]))
            {
                miu[i*prim[j]]=0;
                break;
            }
            miu[i*prim[j]]=-miu[i];
        }
    }
}
 
long long calc(long long x)
{
    long long tot=0,t;
    for (long long i=1;i<=sqrt(x);i=t+1) 
    {
        t=x/(x/(i*i)); t=sqrt(t);
        //printf("%d %d\n",i,t);
        tot+=(miu[t]-miu[i-1])*(x/(i*i));
        //printf("%d\n",tot);
        //printf("%d %d\n",miu[t],miu[i-1]);
    }
    return tot;
}
 
int main()
{   
    prepare();
    for (long long i=1;i<=50000;i++) miu[i]+=miu[i-1];
    //printf("%d",calc(1));
    //for (long long i=1;i<=100;i++) printf("%d ",miu[i]);
    long long task;
    scanf("%lld",&task);
    while (task--)
    {
        long long l=1ll,r,n,ans;
        scanf("%lld",&n);
        r=n<<1;
        while (l<=r)
        {
            long long mid=(l+r)>>1;
            //printf("%d %d %d\n",l,r,mid);
            if (calc(mid)>=n)
            {
                ans=mid;
                r=mid-1ll;
            } else l=mid+1ll;
            //printf("%d %d %d\n",l,r,mid);
        }
        printf("%lld\n",ans);
    }
    return 0;
}