[bzoj2440]完全平方数(二分+mobius反演)

解题关键：由容斥原理得，num=1的倍数的数量−一个质数平方数(9,25,49...)的倍数的数量+两个质数的积平方数(36,100,225...)的数量−三个质数......

这道题用莫比乌斯的正向函数表达式理解较容易

此题让自己理解了只要与倍数相关即可用mobius。

此题还需要注意的一点，是平方数只需要反演质数。貌似是常识

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 ll t,n;

 inline ll read(){

     char k=;char ls;ls=getchar();for(;ls<''||ls>'';k=ls,ls=getchar());

     ll x=;for(;ls>=''&&ls<='';ls=getchar())x=(x<<)+(x<<)+ls-'';

     if(k=='-')x=-x;return x;

 }

 //莫比乌斯函数线性筛法

 const int maxn=+;

 bool vis[maxn];

 int prime[maxn],mu[maxn];

 void init_mu(int n){

     int cnt=;

     mu[]=;

     for(int i=;i<n;i++){

         if(!vis[i]){

             prime[cnt++]=i;

             mu[i]=-;

         }

         for(int j=;j<cnt&&i*prime[j]<n;j++){

             vis[i*prime[j]]=;

             if(i%prime[j]==)   {mu[i*prime[j]]=;break;}

             else { mu[i*prime[j]]=-mu[i];}

         }

     }

 }

 bool check(ll x){

     ll ans=;

     for(ll i=;i*i<=x;i++){

         ans+=mu[i]*(x/(i*i));

     }

     return ans>=n;

 }

 ll erfen(ll l,ll r){

     while(l<r){

         ll mid=(l+r)>>;

         if(check(mid)) r=mid;

         else l=mid+;

     }

     return r;

 }

 int main(){

     init_mu();

     t=read();

     while(t--){

         n=read();

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

     }

 }