洛谷P4318 完全平方数

@Pelom  November 6, 2019

题意

求第$k$个不含完全平方数因子的数

数据范围:$k \le 10^9$

题解

二分这个数,然后验证其排名是否$\ge k$
对于计算$n$以内的无平方因子数的个数,可以用到容斥原理
$$ans=含0个质数的平方因子的个数-含1个质数的平方因子的个数+含2个质数的平方因子的个数 \dots$$
注意到每个数的容斥系数恰好为莫比乌斯函数$\mu(i)$,上式即为$$\sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \mu(i) \lfloor \frac{n}{i^2} \rfloor$$
预处理莫比乌斯函数计算

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e5;
int t,k;
int l,r,ans,cnt;
int pri[N+1],mu[N+1];
bool isp[N+1];
inline void sift(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!isp[i]){
            mu[i]=-1;
            pri[++cnt]=i;
        }
        for(int j=1;j<=cnt && i*pri[j]<=n;j++){
            isp[i*pri[j]]=1;
            if(i%pri[j]==0)
                break;
            mu[i*pri[j]]=-mu[i];
        }
    }
}
inline bool check(int n){
    int res=0;
    for(int i=1;i*i<=n;i++)
        res+=mu[i]*(n/(i*i));
    return res>=k;
}
int main(){
    sift(N);
    scanf("%d",&t);
    for(;t--;){
        scanf("%d",&k);
        l=k,r=k<<1;
        for(l--,r++;l<=r;){
            int mid=(1ll*l+r)>>1;
            if(check(mid)){
                r=mid-1;
                ans=mid;
            }
            else l=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

另一种推式子的方法

知道

$$ \mu(n)= \left\{ \begin{aligned} & 1 &&,n=1 \\ & (-1)^k &&,n=p_1p_2 \dots p_k \\ & 0 &&,otherwise(含平方因子) \end{aligned} \right. $$

那么$n$以内的无平方因子数的个数即为

$$ \begin{aligned} \sum_{i=1}^n \mu^2(i) &= \sum_{d^2|n} \mu(d) \\ &= \sum_{d=1}^{\lfloor \sqrt{n} \rfloor} \mu(d) \lfloor \frac{n}{d^2} \rfloor \end{aligned} $$


添加新评论