Skip to content

莫比乌斯反演

莫比乌斯函数

定义

  1. 莫比乌斯函数\(\mu(n)\)的定义域是\(N\)
  2. \(\mu(1)=1\)
  3. 当\(n\)存在平方因子时,\(\mu(n)=0\)
  4. 当\(n\)是素数或奇数个不同素数之积时,\(\mu(n)=-1\)
  5. 当\(n\)是偶数个不同素数之积时,\(\mu(n)=1\)

线性筛求\(\mu(n)\)

void prime(){
    mu[1]=1;
    for(int i=2;i<=n;++i){
        if(!vis[i]) p[++m]=i,mu[i]=-1;//只有一个素因子，则mu[n]=-1
        for(int j=1;j<=m && p[j]*i<=n;++j){
            vis[p[j]*i]=1;
            if(i%p[j]==0)break;//如果p[j]|i,说明一定存在平方因子，则跳过不更新mu[p[j]*i]，这将意味着mu[p[j]*i]永远为0
            mu[p[j]*i]=-mu[i];//如果mu[i]=0,则mu[p[j]*i]同样为0；如果mu[i]!=0,则mu[p[j]*i]加入一个新的素因子p[j]，应当乘-1
        }
    }   
}

性质

1) 对于任意正整数\(n\),\(\sum_{d|n}\mu(d)=[n=1]\)

2) 对于任意正整数\(n\),\(\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}\)

证明

性质1.

  1. 当\(n=1\)时，原式\(=\mu(1)=1\),成立

  2. 当\(n\not =1\)时，将\(n\)分解成\(p_1^{a_1}p_2^{a_2}...p_k^{a_k}\)

只有所有质因子的个数为\(1\)时\(\mu(d)\)不为\(0\),所以假设由\(x\)个不同质因子的\(d\)有\(C_{k}^{x}\)个，则

\[\sum_{d|n}\mu(d)=C_k^0-C_k^1+C_k^2-...=\sum_{i=0}^k(-1)^iC_k^i\\ 又\because 二项式展开公式为(X+Y)^n=\sum_{i=0}^nC_n^iX^iY^{n-i}\\ \therefore 带入X=-1,Y=1\\ \sum_{i=0}^k(-1)^iC_k^i=[1+(-1)]^k=0 \]

性质2

\[即证n\sum_{d|n}\frac{\mu(d)}d=\phi(n)\\ 令F(n)=n,f(n)=\phi(n),则\\ f(n)=n\sum_{d|n}\frac{\mu(d)}d=\sum_{d|n}\frac{n\mu(d)}d=\sum_{d|n}\mu(d)\frac{n}d=\sum_{d|n}\mu(d)F(\frac nd)\\ 同时，上式成立的条件是F(n)=\sum_{d|n}f(d),即\\ n=\sum_{d|n}\phi(d)\\ 这个式子在欧拉函数的笔记中以证明。\\ 故原命题得证。\]

莫比乌斯反演

定理

\[设f(n)和F(n)是定义在正整数集合上的两个函数\\ F(n)=\sum_{d|n}f(d)=\sum_{d|n}f(\frac nd)\\ 则f(n)=\sum_{d|n}\mu(d)F(\frac nd)=\sum_{d|n}\mu(\frac nd)F(d)\\ 或：\\ F(n)=\sum_{n|d}f(d)\\ 则f(n)=\sum_{n|d}\mu(\frac dn)F(d)\]

套路

套路1:优先枚举\(\gcd k\)

套路2:\(\gcd(i,j)=k等价于 \gcd(\frac ik,\frac jk)=1\)

套路3:莫比乌斯函数的性质\(\sum_{d|n}\mu(d)=[n=1]\)

套路4:优先枚举\(d\)

套路5:设\(dk=T\)

P2257

废话不说，直接开始推导。

\[ 求\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)\in prime]\\ =\sum_{k=1}^n\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=k] (k\in prime)\\ = \sum_{k=1}^n\sum_{i=1}^{\lfloor \frac nk \rfloor}\sum_{j=1}^{\lfloor \frac mk\rfloor } [gcd(i,j)=1] (k\in prime)\\ \because \sum_{d|n}\mu(d)=[n=1]\\ \therefore \sum_{d|\gcd(i,j)}\mu(d)=[\gcd(i,j)=1\\ \therefore =\sum_{k=1}^n\sum_{i=1}^{\lfloor \frac nk \rfloor}\sum_{j=1}^{\lfloor \frac mk\rfloor } \sum_{d|\gcd(i,j)}\mu(d)(k\in prime)\\ \because d|\gcd(i,j),\therefore i,j是d的倍数\\ 又\because d_{max}=\lfloor \frac nk\rfloor\\ \therefore = \sum_{k=1}^n\sum_{d=1}^{\lfloor \frac nk\rfloor}\mu(d)* \lfloor \frac n{kd}\rfloor* \lfloor \frac m{kd}\rfloor (k\in prime)（注_1）\\ 设T=kd,则T_{max}=k*\lfloor \frac nk\rfloor=n\\ \therefore 原式=\sum_{T=1}^n\lfloor \frac nT\rfloor* \lfloor \frac mT\rfloor \sum_{k|T,k\in prime}\mu(\frac Tk)(注_2) \]

这样后面可以在线性筛时做\(O(n)\)预处理+前缀和，前面可以做\(O(T\sqrt n)\)整除分块.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10,M=1e7+10;
typedef long long ll;
int p[M],mu[M],vis[M],sum[M],f[M];
int m,n,T;
void prime(){
    mu[1]=1;
    for(int i=2;i<M;++i){
        if(!vis[i]) p[++m]=i,mu[i]=-1;
        for(int j=1;j<=m && p[j]*i<M;++j){
            vis[p[j]*i]=1;
            if(i%p[j]==0){mu[p[j]*i]=0;break;}
            mu[p[j]*i]=-mu[i];
        }
    }   
    for(int j=1;j<=m;++j){
        for(int i=1;i*p[j]<M;++i){
            f[i*p[j]]+=mu[i];
        }
    } 
    for(int i=1;i<M;++i)sum[i]=sum[i-1]+f[i];   
}
void solve(){
    ll ans=0;
    for(int l=1,r=0;l<=n;l=r+1){
        r=min(n/(n/l),m/(m/l));
        ans+=(ll)(sum[r]-sum[l-1])*(ll)(n/l)*(ll)(m/l);
    }
    printf("%lld\n",ans);
}
int main(){
    prime();
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);if(n>m)swap(n,m);
        solve();
    }
    return 0;
}

  • 注_1: 这里的变换时因为每一个\(d\)都由许多个\(i，j\)枚举而来，所以枚举\(d\)时直接乘上能转移过来的\(i,j\)的最大个数即可，而\(d\)最大能取到\(n\) (\(\gcd(n,m)=n\)时)

  • 注_2: 这里的变换相当于\(1\)的逆操作,\(1\)时由大变小，而\(2\)时由小变大。一个\(T\)能转移到的所有\(d\)为\(d=\frac Tk (k|T,k\in prime)\),所以对这些\(d\)有贡献\(\mu(\frac Tk)\)，要加在一起。

~~全long long计算真的慢，比int转long long 慢一倍~~

P3455

模板题.

这里给出一个与P2577不同的推式子的方法，大同小异

$$f(k)=\sum_{i=1}^a\sum_{j=1}^b[gcd(i,j)=k]\ F(n)=\sum_{n|k}f(k)=\lfloor\frac an\rfloor\lfloor \frac bn\rfloor\ f(n)=\sum_{n|k}\mu(\lfloor \frac kn\rfloor)F(k) $$ 之后退出来的式子与用\(\sum_{d|n}\mu(d)=[n=1]\)推出来的一样。

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long 
using namespace std;
const int N=1e5+10,M=1e6+10;
int a,b,d,n,m,T;
int p[M],mu[M],vis[M],sum[M];
void prime(){
    mu[1]=1;
    for(int i=2;i<M;++i){
        if(!vis[i]) p[++m]=i,mu[i]=-1;
        for(int j=1;j<=m && i*p[j]<M;++j){
            vis[i*p[j]]=1;
            if(i%p[j]==0) break;
            mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1;i<M;++i)sum[i]=sum[i-1]+mu[i];
}
void solve(){
    ll ans=0;
    n=a/d,m=b/d;
    if(n>m)swap(n,m);
    for(int l=1,r=0;l<=n;l=r+1){
        r=min(n/(n/l),m/(m/l));
        ans+=(ll)(sum[r]-sum[l-1])*(ll)(n/l)*(ll)(m/l);
    }
    printf("%lld\n",ans);
}
int main(){
    prime();
    scanf("%d",&T);
    for(int i=1;i<=T;++i){
        scanf("%d%d%d",&a,&b,&d);
        solve();    
    }
    return 0;
}

P3327

\[ 已知d(i* j)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1] （注_1）\\ 则原式= \sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]\\ = \sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|\gcd(x,y)}\mu(d)\\ 将枚举项i,j改为枚举x,y\\ =\sum_{x=1}^n \sum_{y=1}^m \lfloor\frac nx\rfloor\lfloor\frac my\rfloor \sum_{d|\gcd(x,y)}\mu(d)\\ 继续枚举d\\ =\sum_{x=1}^n \sum_{y=1}^m \lfloor\frac nx\rfloor\lfloor\frac my\rfloor \sum_{d=1}^n\mu(d)[d|\gcd(x,y)]\\ 因为\mu(d)与x,y无关，可以提到前面去\\ =\sum_{d=1}^n\mu(d)\sum_{x=1}^n\sum_{y=1}^m \lfloor\frac nx\rfloor\lfloor\frac my\rfloor [d|\gcd(x,y)]\\ 将枚举项x,y改为dx,dy,则[d|\gcd(x,y)]恒满足，可以去掉\\ = \sum_{d=1}^n\mu(d)\sum_{x=1}^{\lfloor\frac nd\rfloor}\sum_{y=1}^{\lfloor\frac md\rfloor} \lfloor\frac n{dx}\rfloor\lfloor\frac m{dy}\rfloor\\ = \sum_{d=1}^n\mu(d)\sum_{x=1}^{\lfloor\frac nd\rfloor}\lfloor\frac n{dx}\rfloor\sum_{y=1}^{\lfloor\frac md\rfloor} \lfloor\frac m{dy}\rfloor\]

此时后面两项可以\(O(n\sqrt n)\)整除分块预处理出\(f\)数组，前面也可以用整除分块\(O(T\sqrt n)\)做。

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=7e4+10;
int p[N],vis[N],mu[N],sum[N];
int T,n,m,cnt;
ll f[N];
void prime() {
    mu[1]=1;
    cnt=0;
    for(int i=2; i<N; ++i) {
        if(!vis[i])p[++cnt]=i,mu[i]=-1;
        for(int j=1; j<=cnt && i*p[j]<N; ++j) {
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
            mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1; i<N; ++i) {
        ll ans=0;
        for(int l=1,r=0; l<=i; l=r+1) {
            r=(i/(i/l));
            ans+=(ll)(r-l+1)*(ll)(i/l);
        }
        f[i]=ans;
    }
    for(int i=1; i<N; ++i)sum[i]=sum[i-1]+mu[i];
}
void solve() {
    ll ans=0;
    for(int l=1,r=0; l<=n; l=r+1) {
        r=min(n/(n/l),m/(m/l));
        ans+=(ll)(sum[r]-sum[l-1])*(ll)(f[m/l])*(ll)(f[n/l]);
    }
    printf("%lld\n",ans);
}
int main() {
    prime();
    scanf("%d",&T);
    for(int i=1; i<=T; ++i) {
        scanf("%d%d",&n,&m);if(n>m) swap(n,m);
        solve();
    }
    return 0;
}
* 注_1:可以当成结论用，具体证明可以看莫比乌斯反演-让我们从基础开始-

P1829

\[ 求\sum_{i=1}^n\sum_{j=1}^m \frac{i* j}{\gcd(i,j)}\\ = \sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m \frac{i* j}{d}[\gcd(i,j)=d]\\ = \sum_{d=1}^n\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor} i* j* d[\gcd(i,j)=1]（注_1）\\ = \sum_{d=1}^n\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor} i* j* d\sum_{k|\gcd(i,j)}\mu(k)\\ = \sum_{d=1}^nd\sum_{k=1}^{\lfloor\frac nd\rfloor}\mu(k)* k^2\sum_{i=1}^{\lfloor\frac n{dk}\rfloor}i\sum_{j=1}^{\lfloor\frac n{dk}\rfloor}j(注_2)\]

此时可以两次分块来做，一次在\(\lfloor\frac n{dk}\rfloor\)时，一次在\(\lfloor\frac nd\rfloor\)时，时间复杂度为\(O(\sqrt n * \sqrt n)=O(n)\)

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N=1e7+10,P=20101009,inv=10050505;
int n,m,cnt;
int vis[N],mu[N],p[N],sum[N];
void prime() {
    mu[1]=1;cnt=0;
    for(int i=2; i<N; ++i) {
        if(!vis[i])p[++cnt]=i,mu[i]=-1;
        for(int j=1; j<=cnt && i*p[j]<N; ++j) {
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
            mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1; i<N; ++i)sum[i]=(sum[i-1]+i*i%P*mu[i])%P;
}
int _solve(int _n,int _m) {
    int tmp=0;
    for(int _l=1,_r=0; _l<=_n; _l=_r+1) { //k
        _r=min(_n/(_n/_l),_m/(_m/_l));
        tmp=(tmp+ (sum[_r]-sum[_l-1])%P* (1+(_n/_l))%P*inv%P*(_n/_l)%P* (1+(_m/_l))%P*inv%P*(_m/_l)%P)%P;
    }
    return tmp;
}
int _solve1(int _n,int _m) {
    int tmp=0;
    for(int _l=1; _l<=_n; ++_l) { //k
        tmp=(tmp+mu[_l]*_l%P*_l%P*(1+_n/_l)%P*(_n/_l)%P*inv%P*(1+_m/_l)%P*(_m/_l)%P*inv%P)%P;
    }
    return tmp;
}
void solve1(){
    int ans=0;
    for(int l=1; l<=n; ++l) { //d
        int _n=n/l,_m=m/l;
        int tmp=_solve(_n,_m);
        ans=(ans+ l*tmp%P)%P;
    }
    ans=(ans%P+P)%P;
    printf("%lld",ans);
}
void solve() {
    int ans=0;
    for(int l=1,r=0; l<=n; l=r+1) { //d
        r=min(n/(n/l),m/(m/l));
        int _n=n/l,_m=m/l;
        int tmp=_solve(_n,_m);
        ans=(ans+ ((l+r)*inv%P*(r-l+1))%P*tmp)%P;
    }
    ans=(ans%P+P)%P;
    printf("%lld",ans);
}
signed main() {
    prime();
    scanf("%lld%lld",&n,&m);
    if(n>m)swap(n,m);
    solve();
    return 0;
}

~~十年OI一场空，不开long long 见祖宗；取模操作也不要吝啬时间复杂度，尽可能地多膜一膜，防止溢出从你我做起~~

  • 注_1: 这里从除以\(d\)变成乘\(d\),即在原始基础上乘了\(d^2\)，是因为\(i,j\)地范围都缩小了\(d\)，而不能忽略后面地\(i* j\)

  • 注_2: 乘\(k^2\)地原因同 注_1

P3911

\[ 设c_i表示i出现的个数，则原题求\\ \sum_{i=1}^N\sum_{j=1}^N\frac{i* j}{\gcd(i,j)}* c_i* c_j,N表示\max_{i=1}^nA_i\\ 1.\\ = \sum_{d=1}^N\sum_{i=1}^N\sum_{j=1}^N\frac{i* j}{d}* c_i * c_j [\gcd(i,j)=d]\\ = \sum_{d=1}^N \sum_{i=1}^{\lfloor \frac Nd\rfloor} \sum_{j=1}^{\lfloor\frac Nd \rfloor}i* j* d* c_{d i} * c_{d j} [\gcd(i,j)=1](注_1)\\ =\sum_{d=1}^N \sum_{i=1}^{\lfloor \frac Nd\rfloor} \sum_{j=1}^{\lfloor\frac Nd \rfloor}i* j* d* c_{d i} * c_{d j} \sum_{k|\gcd(i,j)}\mu(k)\\ =\sum_{d=1}^Nd\sum_{k=1}^{\lfloor\frac Nd \rfloor}\mu(k) k^2(\sum_{i=1}^{\lfloor\frac N {dk}\rfloor}i* c_{kdi})(\sum_{j=1}^{\lfloor\frac N {dk}\rfloor}j* c_{kdj})\\ 2.\\ = \sum_{d=1}^N\sum_{i=1}^N\sum_{j=1}^N\frac{i* j}{d}* c_i * c_j [\gcd(i,j)=d]\\ = \sum_{d=1}^N \sum_{i=1}^{\lfloor \frac Nd\rfloor} \sum_{j=1}^{\lfloor\frac Nd \rfloor}i* j* d* c_{d i} * c_{d j} [\gcd(i,j)=1]\\ =\sum_{d=1}^N \sum_{i=1}^{\lfloor \frac Nd\rfloor} \sum_{j=1}^{\lfloor\frac Nd \rfloor}i* j* d* c_{d i} * c_{d j} \sum_{k|\gcd(i,j)}\mu(k)\\ =\sum_{d=1}^N d\sum_{k=1}^{\lfloor \frac Nd\rfloor}\mu(k)k^2\sum_{i=1}^{\lfloor \frac N{kd}\rfloor} \sum_{j=1}^{\lfloor\frac N{kd} \rfloor}i* j * c_{d ki} * c_{d kj} \\ 设T=dk,则\\ = \sum_{T=1}^N T(\sum_{i=1}^{\lfloor \frac NT \rfloor} i* c_{iT})^2 \sum_{k|T}\mu(k)k\]
  • 注_1: 因为\(i,j\)的大小减小，而\(c\)的下标不能变，所以一定要乘\(d\)