题解 P1390 【公约数的和】

Lates · 2020-03-20 09:30:42 · 题解

莫比乌斯反演入门题

前置芝士

数论分块，一点点莫比乌斯反演

正文

可以考虑先求

\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)

然后再去重。

可以想到枚举n以内的p，把对答案的贡献改成p\times gcd(i,j)=p的数的个数

\sum_{p=1}^{n}p\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)=p]

化简式子

\sum_{p=1}^{n}p\sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor }\sum_{j=1}^{\left \lfloor \frac{n}{p} \right \rfloor }[gcd(i,j)=1]

因为[gcd(i,j)=1]只有gcd(i,j)=1有1的贡献，否则没有，所以可以替换为\varepsilon(gcd(i,j))

\varepsilon(x)$即为当$x=1$时对答案贡献为$1$，否则为$0

所以现在转化为了

\sum_{p=1}^{n}p\sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor }\sum_{j=1}^{\left \lfloor \frac{n}{p} \right \rfloor }\varepsilon(gcd(i,j))

由Dirichlet卷积得

\varepsilon =\mu*1 \Leftrightarrow \varepsilon(n)=\sum_{d|n}\mu(d)

所以原式转化为

\sum_{p=1}^{n}p\sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor }\sum_{j=1}^{\left \lfloor \frac{n}{p} \right \rfloor }\sum_{d|gcd(i,j)}\mu(d)

转化一下求和顺序

\sum_{p=1}^{n}p\sum_{d=1}{\mu(d)}\sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor }[d\ |\ i]\sum_{j=1}^{\left \lfloor \frac{n}{p} \right \rfloor}[d\ | \ j]

后面两个即为求\left \lfloor \frac{n}{p} \right \rfloor中d的倍数，易知其答案为\left \lfloor \frac{n}{pd} \right \rfloor

所以答案转化为

\sum_{p=1}^{n}p\sum_{d=1}\mu(d)\left \lfloor \frac{n}{pd} \right \rfloor\left \lfloor \frac{n}{pd} \right \rfloor

后面那玩意用数论分块和前缀和即可。

ans=\frac{\sum_{p=1}^{n}p\sum_{d=1}\mu(d)\left \lfloor \frac{n}{pd} \right \rfloor\left \lfloor \frac{n}{pd} \right \rfloor-\frac{n(n+1)}{2}}{2}

Code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long 
inline int read(){
    register int x=0,f=0,ch=getchar();
    while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
    return f?-x:x;
}
const int MAX=2000005;
int n,tot,p[MAX],f[MAX],mu[MAX];
inline void Gmu(){
    mu[1]=1;tot=0;
    for(register int i=2;i<=n;++i){
        if(!f[i]){
            p[++tot]=i;
            mu[i]=-1;
        }
        for(register int j=1;j<=tot&&i*p[j]<=n;++j){
            f[i*p[j]]=1;
            if(i%p[j]==0){
                mu[i*p[j]]=0;
                break;
            }
            mu[i*p[j]]=-mu[i];
        }
    }
    for(register int i=1;i<=n;++i)mu[i]+=mu[i-1]; 
} 
int res,ans;
inline void solve(int n,int p){
    res=0;
    for(register int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        res+=(mu[r]-mu[l-1])*(n/l)*(n/l);
    }
    ans+=res*p;
}
signed main(){
    n=read();
    Gmu();
    for(register int p=1;p<=n;++p)solve(n/p,p);
    printf("%lld\n",(ans-(n*(n+1)>>1))>>1);
    return 0;
}

写得有什么问题麻烦私信笔者，谢谢