Eva

Time Limit: 10 Sec  Memory Limit: 128 MB
Description

小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些
数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而
这丝毫不影响他对其他数的热爱。 
这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一
个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了
小X。小X很开心地收下了。 
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？

Input 

包含多组测试数据。文件第一行有一个整数 T，表示测试
数据的组数。 
第2 至第T+1 行每行有一个整数Ki，描述一组数据，含义如题目中所描述。 

Output 

含T 行，分别对每组数据作出回答。第 i 行输出相应的
第Ki 个不是完全平方数的正整数倍的数。

Sample Input

4 
1
13
100
1234567

Sample Output

1 
19
163
2030745

HINT 

对于 100%的数据有 1 ≤ Ki ≤ 10^9

,    T ≤ 50

Source

/**************************************************************

    Problem: 2440

    User: ictsing

    Language: C++

    Result: Accepted

    Time:4312 ms

    Memory:2180 kb

****************************************************************/

 

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

typedef long long ll;

const int mt=100000+5;

int u[mt],pri[mt];

bool ovo[mt];

inline ll readll()

{

    ll num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void mobius()

{

    u[1]=1;

    for(ll i=2;i<=mt;i++)

    {

        if(!ovo[i]) pri[++pri[0]]=i,u[i]=-1;

        for(ll j=1;j<=pri[0]&&i*pri[j]<=mt;j++)

        {ovo[i*pri[j]]=1;

        if(i%pri[j]==0) {u[i*pri[j]]=0;break;}

        else u[i*pri[j]]=-u[i];}

    }

}

ll check(ll t)

{

    ll e=(ll)sqrt(t),ans=0;

    for(ll i=1;i<=e;i++)

        ans+=u[i]*(t/(i*i));//用mobius来统计因数个数 

    return ans;

}

void getans(ll x)//二分答案是必须的 

{

    ll l=1,r=x<<1;

    while(l+1<r)

    {

        ll mid=(l+r)>>1;

        if(check(mid)<x) l=mid;

        else r=mid;

    }

    printf("%lld\n",r);

}

int main()

{

    mobius();

    ll t=readll(),ovo;

    while(t--) ovo=readll(),getans(ovo);

    return 0;

}