[中山市选2011]完全平方数 ——莫比乌斯函数

题意：

求第k大的，不是任意完全平方数（除了1）整数倍的数。

求第k大的不含有完全平方数因子的数。

T<=50组询问，K<=1e9

题解：

考虑完全平方数的倍数，就直接考虑质数的平方数的倍数就好。

第k大直接求不好求。也不能循环判断。

因为大小是单调的（废话），所以可以二分。

对于mid，可以用所有的小于mid的质数平方数判断有多少个是不合法的。

但是，对于pri^2,prj^2 ,两者的最小公倍数即(pri*prj)^2的倍数会被多减一次。

所以考虑到了容斥。。。但是2^sum(pr)的复杂度太高了。

我们先列出式子：

对于二分出来的mid ： ans=(-1)^k*mid/(p1*p2*...pk)^2

注意到，当k为奇数的时候，为-1，偶数为+1，

而且，p1*p2*...*pk=d的质因子个数恰好是k个。而且d<=sqrt(2e9)

所以(-1)^k= u(d) u是莫比乌斯函数。

所以对于每个mid，循环一遍i从2到sqrt(2e9)，象征p1*p2*....pk的所有情况。

如果i有平方因子，容斥中一定不会有这一项，而u（i）=0，恰好符合容斥中没有这一项的事实。

通过莫比乌斯函数更新答案。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=44728+5;
int u[N],T,K;
int pr[N],cnt;
bool vis[N];
void sieve(){
    u[1]=1;
    for(int i=2;i<=N-1;i++){
        if(!vis[i]){
            u[i]=-1;
            pr[++cnt]=i;            
        }
        for(int j=1;j<=cnt;j++){
            if(pr[j]*i>N-1) break;
            vis[pr[j]*i]=1;
            if(i%pr[j]==0) {
            u[pr[j]*i]=0;break;
            }
            else u[pr[j]*i]=-u[i];
        }
    }
}
bool che(ll x){
    ll ret=x;
    for(ll i=2;i*i<=x;i++) ret+=u[(int)i]*(x/(i*i));
    return ret>=K;
}
int main()
{
    sieve();
    scanf("%d",&T);
    while(T--){
        scanf("%d",&K);
        ll l=1,r=N*N;
        ll op;
        while(l<=r){
            ll mid=(l+r)>>1;
            if(che(mid)) op=mid,r=mid-1;
            else l=mid+1;
        } 
        printf("%lld
",op);
    }
    return 0;
}

upda 2019.1.18

感觉应该不用莫比乌斯函数也能做

直接找出sqrt以内的质数

然后暴力2^pr容斥即可

由于质数的连乘积不会大于根号n

而每一个数只能被一个质数连乘积表示

所以加上各种剪枝之后

复杂度期望也是O(sqrt(n))的，理论会更小。但是常数极大。

可过。

(−1)kmidp1∗p2∗...∗pk