莫比乌斯反演

运用莫比乌斯反演，我们可以将一些函数转化，从而降低计算难度。在一些于 gcd 相关的算法问题中，莫比乌斯反演非常重要。

狄利克雷卷积

英文名为 Dirichlet 卷积，以下用符号 $\ast *$ 表示。

$(f\ast g)(n)={\sum }_{d\mathrm{\mid }n}f(d)\times g(\frac{n}{d})(f*g)(n)=\backslash sum\_\{d|n\}f(d)\backslash times\; g(\backslash frac\{n\}\{d\})$

狄利克雷卷积单位元记做 $e(n)=[n=1]e(n)=[n=1]$，方括号中的等式成立则值为 $11$，否则为 $00$。

单位元的意义为：$(f\ast e)(n)=f(n)(f*e)(n)=f(n)$

莫比乌斯函数

函数值：

• 当 $n=1n=1$ 时，$\mu (n)=1\backslash mu(n)=1$

• 当 $nn$ 含有次数大于 $11$ 的质因数时，$\mu (n)=0\backslash mu(n)=0$

• 当 $nn$ 不含次数大于 $11$ 的质因数时， $\mu (n)=(-1{)}^k\backslash mu(n)=(-1)^k$，其中 $kk$ 为质因数的个数

函数性质：$(u\ast 1)(n)={\sum }_{d\mathrm{\mid }n}\mu (d)=[n=1]=e(n)(u*1)(n)=\backslash sum\_\{d|n\}\backslash mu(d)=[n=1]=e(n)$

证明：

当 $nn$ 不为 $11$ 时，为了去除 $\mu (n)=0\backslash mu(n)=0$ 的情况，将 $nn$ 的所有不同质因数乘起来得到 $n^{\mathrm{\prime }}n\text{'}$。

${\sum }_{d\mathrm{\mid }{n}^{\mathrm{\prime }}}\mu (d)={\sum }_{d\mathrm{\mid }n}\mu (d)\backslash sum\_\{d|n\text{'}\}\backslash mu(d)=\backslash sum\_\{d|n\}\backslash mu(d)$

因为 $n^{\mathrm{\prime }}n\text{'}$ 所有质因数的次数都是 $11$ 了，所以枚举其因数就是每个质因数的选与不选。

利用二项式定理，其中 $kk$ 和上文一样表示 $nn$ 中质因数的个数：

${\sum }_{d\mathrm{\mid }{n}^{\mathrm{\prime }}}\mu (d)={\sum }_{i=0}^k{(}_i^k)\times (-1{)}^i={\sum }_{i=0}^k{(}_i^k)\times (-1{)}^i\times 1^{(k-i)}=(-1+1{)}^k=0\backslash sum\_\{d|n\text{'}\}\backslash mu(d)=\backslash sum^k\_\{i=0\}(^k\_i)\backslash times(-1)^i=\backslash sum^k\_\{i=0\}(^k\_i)\backslash times(-1)^i\backslash times\; 1^\{(k-i)\}=(-1+1)^k=0$

当 $nn$ 为 $11$ 时，显然 $kk$ 就等于 $00$ 了，所以最后的值为 $11$。

void get_mu(int n){ //线性筛求莫比乌斯函数
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){prim[++cnt]=i;mu[i]=-1;}
        for(int j=1;j<=cnt&&prim[j]*i<=n;j++){
            vis[prim[j]*i]=1;
            if(i%prim[j]==0)break;
            else mu[i*prim[j]]=-mu[i];
        }
    }
 }

莫比乌斯反演

若 $f=g\ast 1f=g*1$，那么 $g=f\ast \mu g=f*\backslash mu$ 。

证明：

将 $f=g\ast 1f=g*1$ 等号两边同时与 $\mu \backslash mu$ 卷积，得到：$f\ast \mu =g\ast 1\ast \mu f*\backslash mu=g*1*\backslash mu$ 。

显然狄利克雷卷积是支持交换律和结合律的，所以变成 $f\ast \mu =g\ast (1\ast \mu )f*\backslash mu=g*(1*\backslash mu)$ 。

又因为莫比乌斯函数性质，$u\ast 1=eu*1=e$，和单位元的意义，所以：

$f\ast \mu =g\ast e=gf*\backslash mu=g*e=g$

例题

P2257 YY的GCD

P2522 [HAOI2011]Problem b

P3172 [CQOI2015]选数

参考资料

莫比乌斯反演 (2020), zhihu [online]. Available from: https://zhuanlan.zhihu.com/p/106775790 [Accessed on June 28 2022]

莫比乌斯反演 (2018), cnblogs [online]. Available from: https://www.cnblogs.com/peng-ym/p/8647856.html [Accessed on June 28 2022]