莫比乌斯反演总结

阅读量：5051 次

发布时间：2019-06-12

本文共 3989 字，大约阅读时间需要 13 分钟。

莫比乌斯反演

1. 定义

对于一个定义在非负整数上的函数 \(f(n)\),定义函数\(F(n)\)。

\[F(n)=\sum_{d|n}f(d)\]

那么有如下结论：

\[f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})\]

其中：

\((1)若d=1,则\;\;\mu(d)=1\;\;\)

\((2)若d=p_1p_2p_3p_4...p_k,即d有k个互异的质因子\;\;\mu(d)=(-1)^k\)

\((3)其他情况下\;\;\mu(d)=0\)

2.莫比乌斯函数的性质&证明

性质1:\[\sum_{d|n}^n\mu(d)=\begin{cases} 1， & 若n=1\\ 0 , & 若n>1 \end{cases}\]

证明：

n=1时显然成立;

n>1时:

\(设n=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k},n_1=p_1p_2p_3...p_k\)

\(设d,d|n_1\;\;所以d|n,若d包含多个相同质因子，则\mu(d)无贡献,反之有贡献\)

那么易知\[\sum_{d|n}^n\mu(d)=\sum_{d'|n_1}^{n_1}\mu(d')\]

\(所以\mu(d)的值与取的质因子个数有关，即\)

\[\sum_{d|n_1}^{n_1}=\sum_i^kC(k,i)*(-1)^i\]

由二项式定理:\[(a+b)^n=\sum^n_{i=0}C(n,i)a^{i}b^{n-i}\]

取\(a=-1,b=1,则\)\[\sum^{n_1}_{d|n_1}=(-1+1)^n=0\;\;\;证毕\]

性质2:

\[\sum^n_{d|n}\dfrac{\mu(d)}{d}=\dfrac{\Phi(n)}{n}\]

莫比乌斯反演定理的证明:

\[左边=\sum^{n}_{d|n}\mu(d)F(\frac{n}{d})=\sum^{n}_{d|n}\mu(d)\sum^{\frac{n}{d}}_{d'|\frac{n}{d}}f(d')=\sum_{d'|n}^nf(d')\sum_{d|\frac{n}{d'}}^{\frac{n}{d'}}\mu(d)=f(n)\]

最后两步的解释：

我们枚举d',因为\(d'|\dfrac{n}{d},所以d'|n,令d'=k\dfrac{n}{d},那么d=k\dfrac{n}{d'},即d|\dfrac{n}{d'},然后当且仅当d'= n时\)

\(\sum_{d|\frac{n}{d'}}^{\frac{n}{d'}}\mu(d)=1,最后结果为f(n)\)

3.莫比乌斯函数的筛法

线性筛法:

int pri[N];int cnt=0;bool vis[N];int mu[N];inline void prepare()//线性筛法求 mu(d){    vis[1]=1;    for(register int i=2;i<=n;i++)    {        if(!vis[i]) {pri[++cnt]=u;mu[i]=-1;}        for(register int j=1;j<=cnt&&((1ll*pri[j]*i)<=n);j++)        {            vis[pri[j]*i]=1;            if(i%pri[j]==0) {mu[i*pri[j]]=0;break;}//此时有两个相同因子            mu[i*pri[j]]=-mu[i];//新加一个相异质数;        }    }    return ;}

4.应用

注:以下除法未说明均为向下取整。

其实莫比乌斯反演还有另一种描述:

\[f(n)=\sum^n_{n|d}\mu(\frac{d}{n})F(d)\]

证明类似：

首先知道若\(nk|d,\)那么 \(n|d,k|d\)。

\(\sum_{n|d}^n\mu(\frac d n)F(d)=\sum_{k=1}^{+∞}\mu(k)F(nk)=\sum^{+∞}_{k=1}\mu(k)\sum_{nk|d'}f(d')\)

\(=\sum_{n|d}f(d)\sum_{k|\frac n d}\mu(k)=f(n)\;\;\;\;当且仅当d=n时\sum_{k|\frac n d}\mu(k)=1\)

一般都用这种

~~担心d会无限增大?F(d)这时就会没贡献了~~

1.一道简单例题:

\(求i从1到n,j从1到m的i,j互质的对数\)

\[即为\sum^n_i\sum^m_j[gcd(i,j)=1]\]

\(那么就设f(x)为n,m内gcd=x的对数,F(x)=\sum_{x|d}f(\frac{d}{x})\)

\(那么推知F(x)表示n,m内x|gcd的对数,\)

现在要求\(f(1)\),套用公式就是:

\(f(1)=\sum_{1|d}^{min(n,m)}\mu(\frac d 1)F(d)\)

即

\(f(1)=\sum_{d=1}^{min(n,m)}\mu(d)F(d)\)

易知\(F(d)=\dfrac n d*\dfrac m d,即为gcd是d的倍数的对数\)

那么\(f(1)=\sum_{d=1}^{min(n,m)}\mu(d)\dfrac n d*\dfrac m d\)

这样我们其实也可以轻松求出\(gcd=k\)的对数,因为\(n,m\)中\(gcd=k\)的数的对数即为\(\dfrac n d,\dfrac m d中,\) \(gcd=1\)的数的对数。

所以就是:

\(f(k)=\sum_{k|d}^{min(n,m)}\mu(\frac d k)F(d)=\sum_{k|d}^{min(n,m)}\mu(\frac d k)\dfrac n d*\dfrac m d\)

\(=\sum^{min(\frac n k,\frac m k)}_{d=1}\mu(d) \dfrac n {kd}*\dfrac m {kd}\;\;\;\)(可以理解为枚举了\(\frac d k),\;\;令n'=\frac n k,m'=\frac mk\)

\(=\sum_{d=1}^{min(n',m')}\dfrac {n'} d*\dfrac {m'} d*\mu(d)\)

然后还可以对除法进行分块，并求出\(\mu(d)\)的前缀和,即可达到每次\(O(\sqrt n)\)的回答

~~虽然预处理有O(n)~~

贴个代码 LupguP2522 [HAOI2011]Problem b

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;inline int read(){ int x=0;char ch=getchar();int t=1; for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=-1; for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48); return x*t;}const int N=5e4+10;int mu[N];typedef long long ll;int pri[N];int cnt;bool vis[N];inline void prepara(){ mu[1]=1;vis[1]=1; for(register int i=2;i<=N;i++) { if(!vis[i]) {pri[++cnt]=i;mu[i]=-1;} for(register int j=1;j<=cnt&&(1ll*pri[j]*i
          
           b) swap(a,b); if(a==0) return 0; a/=c;b/=c; register ll res=0; register int l,r; for(l=1;l<=a;l=r+1) { r=min(a/(a/l),b/(b/l)); if(r>a) r=a; res+=1ll*(mu[r]-mu[l-1])*(a/l)*(b/l); } return res;}int main(){ prepara(); int T=read(); while(T--) { register int a=read(),b=read(),c=read(),d=read(),e=read(); if(e==0) {puts("0");continue;} register ll ans1=calc(b,d,e)-calc(a-1,d,e); register ll ans2=calc(b,c-1,e)-calc(a-1,c-1,e); //这题还要容斥一波 printf("%lld\n",ans1-ans2); }}