「算法笔记」莫比乌斯反演

莫比乌斯反演是数论中的重要内容。对于一些函数，如果很难直接求出它的值，而容易求出其倍数和或约数和，那么可以通过莫比乌斯反演求得原函数的值。

积性函数

定义

若 $\gcd(x,y)=1$ 且 $f(xy)=f(x)f(y)$，则 $f(n)$ 为积性函数。

性质

若 $f(x)$ 和 $g(x)$ 均为积性函数，则以下函数也为积性函数：

$$\begin{align*} h(x) & = f(x^p) \\ h(x) & = f^p(x) \\ h(x) & = f(x)g(x) \\ h(x) & = \sum_{d\mid x}f(d)g(\frac{x}{d}) \\ \end{align*}$$

例子

$$\begin{array} \text{约数个数函数} & d(n)=\sum_{d\mid n}1 \\ \text{约数和函数} & \sigma(n)=\sum_{d\mid n}d \\ \text{约数}\ k\ \text{次幂函数} & \sigma_k(n)=\sum_{d\mid n}d^k \\ \text{欧拉函数} & \varphi(n)=\sum_{i=1}^n [\gcd(i,n)=1] \\ \text{莫比乌斯函数}& \mu(n)= \begin{cases} 1 & n=1 \\ (-1)^k & c_{1,2,\cdots,k}=1\quad(n=\prod_{i=1}^k {p_i}^{c_i}) \\ 0 & c_i>1 \end{cases} \end{array}$$

---

Dirichlet 卷积

定义

定义两个数论函数 $f,g$ 的 $\text{Dirichlet}$ 卷积为

$$(f\ast g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})$$

性质

$\text{Dirichlet}$ 卷积满足交换律、结合律、分配律。

其中 $\varepsilon$ 为 $\text{Dirichlet}$ 卷积的单位元（任何函数卷 $\varepsilon$ 都为其本身）

例子

$$\begin{align*} \varepsilon=\mu\ast 1 & \Leftrightarrow\varepsilon(n)=\sum_{d\mid n}\mu(d) \\ d=1\ast 1 & \Leftrightarrow d(n)=\sum_{d\mid n}1 \\ \sigma=d\ast 1 & \Leftrightarrow\varepsilon(n)=\sum_{d\mid n}d \\ \varphi=\mu\ast\operatorname{ID} & \Leftrightarrow\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d}) \\ \end{align*}$$

---

莫比乌斯函数

定义

$\mu$ 为莫比乌斯函数

性质

莫比乌斯函数不但是积性函数，还有如下性质：

$$\mu(n)= \begin{cases} 1 & n=1 \\ 0 & n\ \text{含有平方因子} \\ (-1)^k & k\ \text{为}\ n\ \text{的本质不同质因子个数} \\ \end{cases}$$

证明

$$\varepsilon(n)= \begin{cases} 1 & n=1 \\ 0 & n\neq 1 \\ \end{cases}$$

其中 $\varepsilon(n)=\sum_{d\mid n}\mu(d)$ 即 $\varepsilon=\mu\ast 1$

设

$$n=\prod_{i=1}^k{p_i}^{c_i},n'=\prod_{i=1}^k p_i$$

那么

$$\sum_{d\mid n}\mu(d)=\sum_{d\mid n'}\mu(d)=\sum_{i=0}^k C_k^i\cdot(-1)^k$$

根据二项式定理，易知该式子的值在 $k=0$ 即 $n=1$ 时值为 $1$ 否则为 $0$，这也同时证明了 $\sum_{d\mid n}\mu(d)=[n=1]$

反演结论：$[gcd(i,j)=1]\Leftrightarrow\sum_{d\mid\gcd(i,j)}\mu(d)$

• 直接推导：如果 $\gcd(i,j)=1$，那么意味着上述结论中的 $n=1$，也就是式子的值是 $1$。反之不满足 $[\gcd(i,j)=1] $，值即为 $0$

• 利用 $\varepsilon$ 函数：根据上一结论，$[\gcd(i,j)=1]\Rightarrow\varepsilon(\gcd(i,j))$，将 $\varepsilon$ 展开即可。

线性筛

由于 $\mu$ 函数为积性函数，因此可以线性筛莫比乌斯函数（线性筛基本可以求所有的积性函数，尽管方法不尽相同）。

代码：

void getMu() {
    mu[1]=1;
    for(int i=2;i<=n;++i) {
        if(!flg[i]) p[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) {
                mu[i*p[j]]=0;
                break;
            }
            mu[i*p[j]]=-mu[i];
        }
    }
}

拓展结论

$$\varphi\ast 1=\operatorname{ID}\quad\operatorname{ID}\ \text{即}\ f(x)=x$$

将 $n$ 分解质因数：$n=\prod_{i=1}^k {p_i}^{c_i}$

首先，因为 $\varphi$ 是积性函数，故只要证明当 $n’=p^c$ 时 $\varphi\ast 1=\sum_{d\mid n’}\varphi(\frac{n’}{d})=\operatorname{ID}$ 成立即可。

因为 $p$ 是质数，于是 $d=p^0,p^1,p^2,\cdots,p^c$

易知如下过程：

$$\begin{align*} \varphi\ast 1 & =\sum_{d\mid n}\varphi(\frac{n}{d}) \\ & =\sum_{i=0}^c\varphi(p^i) \\ & =1+p^0\cdot(p-1)+p^1\cdot(p-1)+\cdots+p^{c-1}\cdot(p-1) \\ & =p^c \\ & =\operatorname{ID} \\ \end{align*}$$

该式子两侧同时卷 $\mu$ 可得 $\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d})$

---

莫比乌斯反演

公式

设 $f(n),g(n)$ 为两个数论函数。

如果有

$$f(n)=\sum_{d\mid n}g(d)$$

那么有

$$g(n)=\sum_{d\mid n}\mu(d)f(\frac{n}{d})$$

证明

暴力计算

$$\sum_{d\mid n}\mu(d)f(\frac{n}{d})=\sum_{d\mid n}\mu(d)\sum_{k\mid \frac{n}{d}}g(k)=\sum_{k\mid n}g(k)\sum_{d\mid \frac{n}{k}}\mu(d)=g(n)$$

用 $\sum_{d\mid n}g(d)$ 来替换 $f(\frac{n}{d})$，再变换求和顺序。最后一步转为的依据：$\sum_{d\mid n}\mu(d)=[n=1]$，因此在 $\frac{n}{k}=1$ 时第二个和式的值才为 $1$。此时 $n=k$，故原式等价于 $\sum_{k\mid n}[n=k]\cdot g(k)=g(n)$

运用卷积

原问题即为：已知 $f=g\ast 1$，证明 $g=f\ast\mu$

易知如下转化：$f\ast\mu=g\ast 1\ast\mu\Rightarrow f\ast\mu=g$（其中 $1\ast\mu=\varepsilon$）

---

问题形式

部分题目的题解可以在本博客中找到！

求解内容	题目
$\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]$	「HAOI 2011」Problem B
$\sum_{i=1}^n\operatorname{lcm}(i,n)$	「SPOJ 5971」LCMSUM
$\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)$	「BZOJ 2154」Crash 的数字表格
$\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c d(ijk)$	「Codeforces 235E」Number Challenge
维护数组 $a$，支持对所有 $\gcd(x,n)=d$ 的 $a_x$ 增加相同的值和前缀和查询	「HDU 4947」GCD Array

本文部分内容引用于 algocode 算法之路，特别鸣谢！