写在前面

这篇博客用来记录一下我学习莫比乌斯反演的过程，以及我是如何理解它的。

期间参考了大量其他博客，这里列出表示感谢：

参考的博客包括但不限于以上这些，有些看过的博客忘记了（逃

另外，如果本篇博客涉及侵权，请您及时联系我修改，以免造成不必要的损失。

前置知识

学习莫比乌斯反演以前，需要先了解的一些前置知识。

积性函数

积性函数是数论中一个非常重要的概念，常常可以利用其性质来进行数论分块优化。

定义

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

扩展：若对于任意 $(x, y)$ 满足 $f(xy) = f(x)f(y)$ ，则称函数 $f(x)$ 为完全积性函数。

性质

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

$h(x) = f(x^p)$
$h(x) = f^p(x)$
$h(x) = f(x)g(x)$
$h(x) = \displaystyle\sum_{d|x} {f(d)g(\frac{x}{d})}$

所有的积性函数都可以用线性筛求。

其实4就是之后会提到的狄利克雷卷积。

常见的积性函数

单位函数： $\varepsilon(n) = [n=1]$ ，也常写作 $\varepsilon$
恒等函数： $id_k(n) = n^k$ ， $id_1(n)$ 常写作 $id(n)$
常数函数 $\bold{1}(n) = 1$ ，常常直接用 $\bold{1}$ 代替
除数函数： $\sigma_k(n) = \displaystyle\sum_{d|n}{d^k}$ ， $\sigma_0(n)$ 通常记为 $d(n)$ ，即常数函数， $\sigma_1(n)$ 通常记为 $\sigma(n)$
欧拉函数： $\varphi(n) = \displaystyle\sum_{i=1}^{n} {[\gcd(i, n) = 1]}$
莫比乌斯函数： $\mu(d) = \begin{cases} 1, & {d = 0} \\ {(-1)} ^k, & {d = p_1 \cdot p_2 \dots p_k}, \forall p_i \not = p_j \\ 0, & {others} \end{cases}$

本篇文章出现的所有 $[x]$ 表示若 $x$ 为真值则 $[x]$ 为1，否则为 $0$ ，且接下来的内容遇到以上函数，可以简写的将尽可能地用简写代替。

狄利克雷卷积

也叫狄利克雷乘积（Dirichlet product），是数论重要知识之一，也是推导、证明莫比乌斯反演的关键。

定义

定义两个数论函数 $f(n), g(n)$ 的狄利克雷卷积为：

$(f(n) * g(n))(n) = \displaystyle\sum_{d|n}{f(d)g(\frac{n}{d})}$

$(f(n) * g(n))(n)$ 常写作 $f * g$

注：数论函数指定义在 $N_+$ 上的函数，满足积性和加性性质。

另外，为了更方便地区分，本文所有 $f*g$ 代表狄利克里卷积，而普通乘法则会写成 $f \cdot g$ 或 $fg$

性质

狄利克雷卷积满足交换律、结合律和分配律（前提是函数均满足加性）。

$f * g = g * f$

$(f * g) * h = f * (g * h)$

$f * (g + h) = f * g + f * h$

$\varepsilon$ 为狄利克雷卷积的幺元（单位元）。

$\forall f(x), x \in N_+ \implies f * \varepsilon = \varepsilon * f = f$

若 $f(x)$ 和 $g(x)$ 均为积性函数，则 $f*g$ 也是积性函数，反之若 $f*g$ 和 $g(x)$ 均为积性函数，则 $f(x)$ 也是积性函数。
若 $g(x)$ 是完全积性函数，且 $h(x) = f*g$ ，则 $f(x) = h* (\mu \cdot g)$

一些例子

$\mu * \bold{1} = \displaystyle\sum_{d|n}{\mu(d)} = \displaystyle\sum_{d|n}{\mu(\frac{n}{d})} = \bold{1} * \mu = \varepsilon$
$\bold{1} * \bold{1} = \displaystyle\sum_{d|n}{1} = d(n)$
$\mu * id = \displaystyle\sum_{d|n}{d \cdot \mu(\frac{n}{d})} = \varphi(n)$
$\varphi * 1 = \displaystyle\sum_{d|n}{\varphi(\frac{n}{d})} = id(n)$

莫比乌斯函数

定义

$\mu(d) = \begin{cases} 1, & {d = 0} \\ {(-1)} ^k, & {d = p_1 \cdot p_2 \dots p_k}, \forall p_i \not = p_j \\ 0, & {others} \end{cases}$

性质

$\mu$ 是积性函数。
$\displaystyle\sum_{d|n}{\mu(d)} = \varepsilon$
$\displaystyle\sum_{d|\gcd(i, j)}{\mu(d)} = \varepsilon(\gcd(i, j)) = [\gcd(i, j) = 1]$
$\displaystyle\sum_{d|n} {\frac{\mu(d)}{d}} = {\frac{\varphi(n)}{n}}$

线性筛

const int MAX_N = 1e6 + 10;
bool vis[MAX_N];
int CNT, prime[MAX_N], mu[MAX_N];

void make_mobius() {
    memset(vis, false, sizeof(vis));
    mu[1] = 1;
    CNT = 0;
    for(int i = 2; i < MAX_N; ++i) {
        if(!vis[i]) {
            prime[++CNT] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= CNT && i*prime[j] < MAX_N; ++j) {
            vis[i*prime[j]] = true;
            if(i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break ;
            } else mu[i * prime[j]] = -mu[i];
        }
    }
}

莫比乌斯反演

定义

设 $f(n)$ 、 $g(n)$ 为两个数论函数，如果

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

那么有

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

根据狄利克雷卷积的性质，当然也可以

$f(n) = \displaystyle\sum_{n|d} {g(d)} \rArr g(n) = \displaystyle\sum_{n|d} {\mu(\frac{d}{n})f(d)}$

证明

其实第一个反演公式还蛮好证明的：

$\because f(n) = \displaystyle\sum_{d|n} {g(d)}$

$\therefore\displaystyle\sum_{d|n} {\mu(d)f(\frac{n}{d})} = \displaystyle\sum_{d|n} {\mu(d)} \displaystyle\sum_{k|\frac{n}{d}}{g(k)}$

根据积性函数性质得

$\displaystyle\sum_{d|n} {\mu(d)} \displaystyle\sum_{k|\frac{n}{d}}{g(k)} = \displaystyle\sum_{d|n}{g(d)} \displaystyle\sum_{k|\frac{n}{d}} {\mu(k)}$

又

$\because \displaystyle\sum_{d|n}{\mu(d)} = [n = 1] \rArr \displaystyle\sum_{k|\frac{n}{d}} {\mu(k)} = \bigg[\frac{n}{d} = 1\bigg]$

$\therefore \displaystyle\sum_{d|n}{g(d)} \displaystyle\sum_{k|\frac{n}{d}} {\mu(k)} = \displaystyle\sum_{d|n}{g(d) \cdot [n=d]} = g(n)$

同理可以证第二个反演公式，证毕。

不过利用狄利克雷卷积证明更快：

第一个反演公式可以转换为

$f = g * \bold{1} \rArr g = \mu * f$

则有

$\mu * f = \mu * g * \bold{1} = g * (\mu * \bold{1}) = g * \varepsilon = g$

证毕。

一些应用

了解了莫比乌斯函数及其反演以后，我们就可以来学习和推导一些东西。

简单例子：推导欧拉函数

假设让你求这样一个式子：

$\sum_{i=1}^{n}{[\gcd(i, n)=1]},(1 \leq n \leq 10^7)$

根据上面提到的莫比乌斯函数的性质3，可以将原式转化为

$\sum_{i=1}^{n}{\sum_{d|gcd(i, n)}\mu(d)}$

当然这样还是不好求，我们需要转换思路，转而去枚举 $d$ ，易知 $d \in [1, n]$ ，则可将上式化为

$\begin{gathered} &\sum_{d=1}^{n}{\mu(d) \sum_{i=1}^{n}{[d|i]}} \\ = &\sum_{d=1}^{n}{\mu(d) \left\lfloor{\frac{n}{d}}\right\rfloor} \end{gathered}$

实际上这就是我们喜闻乐见的欧拉函数 $\varphi(n)$ 。

简单例子扩展

假设现在让你求：

$\sum_{i=1}^{n}\sum_{j=1}^{m}{[\gcd(i, j)=k]},(1 \leq k \leq n \leq m \leq 10^5)$

注意：从这里开始若下文的 $n$ 、 $m$ 没有特殊说明，都是这个量级。

看起来比简单例子难很多？实际上没有，我们依然可以用简单例子的思路。

当然，第一件事是将 $[\gcd(i, j) = k]$ 转换成 $[\gcd(i, j) = 1]$

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

这一步应该很好理解吧？相当于 $i, j$ 都除掉最大公因数 $k$ （逃

接下来的一顿操作就和之前一样了

$\begin{gathered} &\sum_{i=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{k}}\right\rfloor}{[\gcd(i, j)=1]} \\ = &\sum_{i=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{k}}\right\rfloor}{\sum_{d|gcd(i, j)}\mu(d)} \\ = &\sum_{d=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}{\mu(d)}\sum_{i=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}{[d|i]}\sum_{j=1}^{\left\lfloor{\frac{m}{k}}\right\rfloor}{[d|j]} \\ = &\sum_{d=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}{\mu(d)\left\lfloor{\frac{n}{kd}}\right\rfloor\left\lfloor{\frac{m}{kd}}\right\rfloor} \end{gathered}$

如果你看到这里能够理解，说明你对莫比乌斯函数已经有一定感觉了。

另一个简单例子：求最大公约数的和

再来求这样一个式子：

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

有了前面莫比乌斯的套路，那我们我们就有了第一步——化 $\gcd$ 为虚无！

这里当然不能直接地将 $\gcd$ 转化为 $\mu$ ，我们需要借助 $\varphi$ 的性质：

$\sum_{d|n}{\varphi(d)} = n \rArr \sum_{d|gcd(i, n)}{\varphi(d)} = \gcd(i, n)$

然后就成功将原式子转化成

$\sum_{i=1}^{n}\sum_{d|gcd(i, n)}{\varphi(d)}$

显而易见地可以用上前面的套路直接再转化成

$\sum_{d=1}^{n}{\varphi(d) \sum_{i=1}^{n}{[d|i]}} \rArr \sum_{d=1}^{n}{\varphi(d) \left\lfloor{\frac{n}{d}}\right\rfloor}$

喜闻乐见地，我们得到了一个和第一个简单例子类似的式子。

自然地，对于这个式子也有一定的扩展，推导方式和之前类似，这里直接给结果。

$\sum_{i=1}^{n}{\sum_{j=1}^{m}\gcd(i, j)} = \sum_{d=1}^{n}{\varphi(d)\left\lfloor{\frac{n}{d}}\right\rfloor\left\lfloor{\frac{m}{d}}\right\rfloor}$

扩展：求最小公倍数的和

$\sum_{i=1}^{n}lcm(i, n) \rArr \sum_{i=1}^{n}{\frac{i \cdot n}{\gcd(i, n)}}$

易知 $\gcd(a, b) = \gcd(b-a, b)$ ，则上式可化为

$\begin{gathered} &\frac{1}{2} \cdot \left({\sum_{i=1}^{n-1}{\frac{i \cdot n}{\gcd(i, n)}} + \sum_{i=1}^{n-1}{\frac{(n-i) \cdot n}{\gcd(n-i, n)}}}\right) + n \\ = &\frac{1}{2} \cdot \sum_{i=1}^{n-1}{\frac{n^2}{\gcd(i, n)}} + n \end{gathered}$

有了之前的经验，我们就要想办法把 $\gcd(i, n)$ 相同的项合并，于是我们枚举 $d = gcd(i, n)$ ，易知共有 $\varphi(\frac{n}{d})$ 个。则上式可化为

$\frac{1}{2} \cdot \sum_{d<n,d|n}^{}{\frac{n^2 \cdot \varphi(\frac{n}{d})}{d}} + n$

再令 $d' = \frac{n}{d}$ 得

$\frac{n}{2} \cdot \sum_{d'>1,d'|n}^{}{d' \varphi(d')} + n$

设 $g(n) = \displaystyle\sum_{d'>1,d'|n}^{}{d' \varphi(d')}$ ，易知 $g(n)$ 是积性函数，可以利用其性质进行线性筛。

这里用了一种巧妙地方式化简，如果用常规的莫比乌斯反演套路推导：

$\begin{gathered} &\sum_{i=1}^{n}lcm(i, n) = \sum_{i=1}^{n}{\frac{i \cdot n}{\gcd(i, n)}} \\ = &n \cdot \sum_{d|n}^{} {\frac{1}{d}} \cdot {\sum_{i=1}^{n} [\gcd(i, n) = d] \cdot i} \\ = &n \cdot \sum_{d|n}^{} {\frac{1}{d}} \cdot {\sum_{i=1}^{\frac{n}{d}} [\gcd(i, \frac{n}{d}) = 1] \cdot i \cdot d} \\ = &n \cdot \sum_{d|n}^{} {\sum_{i=1}^{\frac{n}{d}} [\gcd(i, \frac{n}{d}) = 1] \cdot i} \end{gathered}$

根据欧拉函数的性质有 $\displaystyle\sum_{\gcd(i, n) = 1}^{n}{i} = \frac{n \cdot \varphi(n)}{2}(n>1)$ ，上式可化为

$n \cdot \sum_{d|n}^{} \frac{\frac{n}{d} \cdot \varphi(\frac{n}{d})}{2}$

同样令 $d' = \frac{n}{d}$ 得

$n \cdot \sum_{d'|n}^{} \frac{d' \varphi(d')}{2}$

推导到这里其实可以发现一个问题：我们会在计算过程中不小心忽略了 $d=n$ 即 $d'=1$ 的情况，所以我们最后需要再加上 $lcm(n, n) = n$ ，即最终答案为：

$n \cdot \sum_{d'>1, d'|n}^{} \frac{d' \varphi(d')}{2} + n$

和我们上面巧妙推导方式的结果是一样的。

有些文章会写成

$\frac{n}{2} \cdot \left(\sum_{d'|n}^{}{d' \varphi(d')} + 1\right)$

本质上是一样的，原因就在于 $n=1$ 时， $\displaystyle\sum_{gcd(i, n) = 1}^{n}{i} = 1$ 。

再扩展：二维最小公倍数求和

$\sum_{i=1}^{n}{\sum_{j=1}^{m}lcm(i, j)} \rArr \sum_{i=1}^{n}{\sum_{j=1}^{m}{\frac{i \cdot j}{\gcd(i, j)}}}$

这里显然不能再用上面非传统的化简思路，还得用回常规套路：

$\begin{gathered} = &\sum_{i=1}^{n}{\sum_{j=1}^{m}{\sum_{d=1}^{n}{\frac{i \cdot j}{d} \cdot [\gcd(i, j) = d]}}} \\ = &\sum_{d=1}^{n}{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}{\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}{\frac{i \cdot j \cdot d^2}{d} \cdot [\gcd(i, j) = 1]}}} \\ = &\sum_{d=1}^{n}{d \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}{\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}{i \cdot j \cdot [\gcd(i, j) = 1]}}} \\ = &\sum_{d=1}^{n}{d \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}{\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}{i \cdot j \cdot \sum_{k|\gcd(i,j)}^{}{\mu(k)}}}} \\ = &\sum_{d=1}^{n}{d \cdot \sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}{\mu(k)} \cdot k^2 \cdot \sum_{i=1}^{\lfloor\frac{n}{dk}\rfloor}{\sum_{j=1}^{\lfloor\frac{m}{dk}\rfloor}{i \cdot j}}} \\ \end{gathered}$