【BZOJ2440】完全平方数

    容斥原理，利用Mobius函数。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=50010;
 
int NotPrime[maxn],Prime[maxn],Primes,Mu[maxn];
int n;
 
void Get_Mu()
{
    Mu[1]=1;
    for (int i=2;i<maxn;i++)
    {
        if (!NotPrime[i])
        {
            Prime[++Primes]=i;
            Mu[i]=-1;
        }
        for (int j=1;j<=Primes && i*Prime[j]<maxn;j++)
        {
            NotPrime[i*Prime[j]]=1;
            if (i%Prime[j]==0)
            {
                Mu[i*Prime[j]]=0;
                break;
            }
            Mu[i*Prime[j]]=-Mu[i];
        }
    }
}
 
bool Check(int x)
{
    int res=0;
    for (int i=1;i*i<=x;i++)
        res+=x/(i*i)*Mu[i];
    return res>=n;
}
 
int main()
{
    Get_Mu();
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        int l=1,r=n*2,mid;
        while (l<r)
            if (Check(mid=l+((r-l)>>1))) r=mid;else l=mid+1;
        printf("%d\n",l);
    }
    return 0;
}