题解：B4308 [蓝桥杯青少年组国赛 2024] 第三题

· · 题解

B4308 题解

题目传送门。

话不多说，切入正题。

题目大意

题目给我们两个数字 m 和 n，要我们求

ans=\sum_{i=m}^{n} \mu(i)

其中 \mu 为莫比乌斯函数。

先简单转化以下，变成

\begin{aligned} ans&=\sum_{i=m}^{n} \mu(i) \\&=\sum_{i=1}^{n}\mu(i)-\sum_{i=1}^{m-1} \mu(i) \end{aligned}

这样问题被转化为了求莫比乌斯函数前缀和。

前置知识

题目给的介绍十分复杂（写给小学生的）。

简单归纳为以下，

\mu(i)=\begin{cases} 1 & \text{ if } x=1 \\ 0 & \text{ if } a^2 \mid x \\ (-1)^{k} & \text{ if } x= {\textstyle \prod_{i=1}^{k} p_i} \end{cases}

其中 a 为大于 1 的正整数，且 p_i 互不相等（1\le i\le k 且 i 为整数）。

程序设计

如果我们采用暴力法的话，时间复杂度为 O(n\sqrt n)，在 n\ge 10^6 的情况下会超时。

这是我们就要拿出我们的线性筛（欧拉筛）了。

先回顾我们的欧拉筛筛素数的方法：

const int N=2e7+10;
int cnt,vis[N],pri[N];
void init()
{
    for(int i=2;i<N;i++){
        if(vis[i]==0){
            vis[i]=1;
            pri[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            if(i*pri[j]>=N){
                break;
            }
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){
                break;
            }
        }
    }
}

这里我们来梳理一遍线性筛求莫比乌斯函数前缀和的方法（建议大家手推一遍），不会的见这里。

1.初始化 \mu(1)=1。

2.若 n 为素数，则 \mu(n)=-1。

3.若 n=pq，其中 p 为素数且 p,q 互质，则 \mu(n)=\mu(p)\mu(q)=-\mu(q)。

4.若存在 p^2\mid n，则 \mu(n)=0。

照着这个思路我们直接开始欧拉筛。

下面给出 AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e7+10;
int cnt,mu[N],vis[N],pri[N],sum[N];    //评估数据尽量别开 long long
void init()
{
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(vis[i]==0){
            mu[i]=-1;
            vis[i]=1;
            pri[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            if(i*pri[j]>=N){
                break;
            }
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){
                mu[i*pri[j]]=0;
                break;
            }
            mu[i*pri[j]]=mu[i]*mu[pri[j]];
        }
    }    //线性筛
    sum[1]=mu[1];
    for(int i=2;i<N;i++){
        sum[i]=sum[i-1]+mu[i];
    }    //求前缀和
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
    int n,m;
    cin>>m>>n;
    cout<<sum[n]-sum[m-1];
    return 0;
}

这样我们就可以在 O(n) 的时间复杂度内解决此题。

扩展算法（可以跳过）

假如 n 达到了 10^8 及以上，那么 O(n) 的算法也无能为力了。

这时我们使用杜教筛（不会的见此）。

给出代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll mu[N],vis[N],pri[N];
unordered_map<ll,ll> summu;
void init()
{
    vis[0]=vis[1]=1;
    mu[1]=1;
    int cnt=0;
    for(int i=2;i<N;i++){
        if(vis[i]==0){
            mu[i]=-1;
            vis[i]=1;
            pri[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            if(i*pri[j]>=N){
                break;
            }
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){
                mu[i*pri[j]]=0;
                break;
            }
            mu[i*pri[j]]=-mu[i];
        }
    }
    for(int i=1;i<N;i++){
        mu[i]+=mu[i-1];
    }
}
ll getsmu(ll x){
    if(x<N){
        return mu[x];
    }
    else if(summu[x]){
        return summu[x];
    }
    ll ans=1;
    for(ll l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans-=(r-l+1)*getsmu(x/l);
    }
    summu[x]=ans;
    return ans;
}
int main(){
    init();
    ll n,m;
    cin>>m>>n;
    cout<<(getsmu(n)-getsmu(m-1));
    return 0;
}

线性筛（欧拉筛）方法

杜教筛方法

也是优化了很多呢！

谢谢阅读！