【题意】T次询问第k小的非完全平方数倍数的数。T<=50，k<=10^9。（即无平方因子数——素因数指数皆为0或1的数）

【算法】数论（莫比乌斯函数）

【题解】考虑二分，转化为询问[1,x]中无平方因子数的个数（x最大为2n）。

运用容斥，答案ans=x - 1个素数的平方的倍数的数的个数 + 2个素数的乘积的平方的倍数的数的个数……

枚举i=[1,√x]的所有数字，系数是莫比乌斯函数，i的平方的倍数的数的个数就是n/(i^2)。

ans=x-Σμ(i)*n/(i^2)，i∈[1,√x]

复杂度O(T*√n)。

注意：二分上届为2n，l+r会爆int。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=50010;int T,tot,n,miu[maxn],prime[maxn];bool mark[maxn];int main(){    scanf("%d",&T);    miu[1]=1;    for(int i=2;i<=50000;i++){        if(!mark[i]){prime[++tot]=i;miu[i]=-1;}        for(int j=1;j<=tot&&i*prime[j]<=50000;j++){            mark[i*prime[j]]=1;            if(i%prime[j]==0)break;            miu[i*prime[j]]=-miu[i];        }    }    while(T--){        scanf("%d",&n);        long long l=0,r=2*n,mid,ans;//        while(l
         
          >1;ans=0;int sq=(int)sqrt(mid);            for(int i=1;i<=sq;i++){                ans+=miu[i]*mid/i/i;            }            if(ans>=n)r=mid;else l=mid+1;        }        printf("%lld\n",l);    }    return 0;}
         
        
       
      

 

定义集合x(素数)表示不是x^2的倍数的数字集合。

则要求集合并，容易知道集合交的补集。