莫比乌斯反演

m256i · 2023-11-09 19:08:19 · 算法·理论

\frak{Praefatio} 前言

本文写于 2023 年 11 月。当时正是 OI 挂飞退役时期，想着总要在 OI 留下点自己的痕迹吧，于是就写了这篇将近 40000 字的文章。

我第一次接触“莫比乌斯反演”这个词是在初一的寒假。当时看了 OI Wiki 和网上一些博客，但是都觉得太复杂看不懂。

直到某次上课推 P1447（当时还是紫，后来降蓝了）式子的时候才意识到“这不就是 \varphi*\mathbf 1=\mathrm{id} 吗”，这才正式开始学习。

在那一个学期里我又补了一堆数学知识，暑假买了《具体数学》。当时觉得自己做了一堆紫黑很 nb，直到后来意识到我除了数学什么都不会，而数学也只会套路做不了思维。

所以初二开始基本就没碰过这些了（OI 也没学过），直到初三开始花了三个月时间整理学习成果，写了几篇博客。

文章的公式（包括行内公式）为了观感舒服都用了 display 样式。

这篇文章的定位是入门和一点进阶，像 P5518 那种过于复杂的题目和某些算法优化要求过高的题目都不包括。选的题目都能用套路方式无脑解决。

文章对数论基础要求不高，但是要求掌握一些求和符号的处理。

积性函数是解析数论中很重要的工具，所以本文也选了一些估阶的题目。如果想要进一步学习可以参考 Apostol 的 Introduction to Analytic Number Theory（国内有影印版，中译本已绝版）。

原来准备写一些组合相关的，比如偏序集上的莫比乌斯反演，但是由于精力不足去年 12 月之后就没更新过。现在对一些表述进行微调之后就作为最终版本了。

这篇文章尽可能做到成体系，此外还包含了 von Mangoldt 函数之类一些小众的东西（虽然 OI 里基本不可能考）。另外注释里给出了人名的读法，这是我加的私货。

有的题目是自己出的，不能保证答案正确，如果有问题请在评论区指出。

希望能够通过这篇文章告诉 OIer：所谓莫比乌斯反演并非什么高级知识或者神秘技巧，而是极其自然的结论。

在这个对计算机人特殊的日子写下这篇前言。

m256i

2024.10.24

\frak{Pars\ A} 基础

\text{Chapter 1} 数论函数

1.1 定义

既然是数论那肯定是研究正整数的。把定义域为正整数（即 \mathbb N^+ 或 \mathbb N^*，也有人写成 \mathbb Z_{>0}）的函数叫做数论函数\text{(number-theoretic function)}或者算术函数\text{(arithmetic function)}。定义域在实数或者复数的函数也可以限制到 \mathbb N 上得到一个数论函数。对值域没有限制，只要是个复数都行。

方便起见，定义数论函数在 0 处的值为 0。

对于数论函数 f，当 p \perp q 时满足 f(pq)=f(p)+f(q) 那么称 f 是加性函数\text{(additive function)}，满足 f(pq)=f(p)f(q) 称 f 是积性函数\text{(multiplicative function)}。如果 p,q 不互质式子仍然成立的话叫完全\text{(completely)}加性函数和完全积性函数。

一些性质是显然的，比如积性函数有 f(1)=1（一般不认为 f(n)=0 是积性函数，即使它满足积性函数的定义），加性函数有 f(0)=0，完全积性函数有 f(n^k)=f^k(n) 之类的。

另外积性函数的乘积也是积性函数，加性函数的和同理，证明也是显然的。

此外还容易证明，假如积性函数 f 和 g 满足以下条件中的任意一个：

• 当 p \perp q 时 g(p) \perp g(q)。

则复合函数 (f \circ g)(n)=f(g(n)) 也是积性函数。

1.2 狄利克雷卷积

现在有两个数论函数 f 和 g，定义 f 和 g 的狄利克雷卷积\text{(Dirichlet}^{[1]}\text{ convolution)}（下文中卷积如果不加说明就是狄利克雷卷积）为：

根据定义显然满足交换律，对结合律来说 (f*g)*h 和 f*(g*h) 都等于 \displaystyle\sum_{xyz=n}f(x)g(y)h(z) 所以也成立。

可以发现 \varepsilon(n)=[n=1] 是一个单位元，现在观察逆元在什么情况下存在。n=1 时 (f*g)(1)=f(1)g(1)，所以 f(1) 不能等于 0（因此加性函数不存在逆元）。对于其他情况：

所以所有 f(1) \ne 0 的函数都有狄利克雷逆元，记作 f^{-1}，即 f(1) \ne 0 的数论函数和卷积运算构成一个交换群。

对于 g(1) \ne 0 的函数定义狄利克雷除法 f/g=f*g^{-1}，关系和一般的乘除法之间是类似的。

证明一个重要的性质：积性函数对卷积运算封闭。换种方式表述就是下面的定理：

例 1.1 （具体数学练习 4.33）证明：两个积性函数的卷积仍然是积性函数。

也就是证明 p \perp q 时有 (f*g)(pq)=(f*g)(p) \times (f*g)(q)。

事实上积性函数对逆元同样封闭。

例 1.2 证明：积性函数的狄利克雷逆元仍是积性函数。

为了完整这里放出一个冗长的证明。后面会给出基于代数的更简单的证明。

首先有 f(1)=f^{-1}(1)=1。假设 pq \ne 1，现在就是证明 p \perp q 时有 f^{-1}(pq)=f^{-1}(p)f^{-1}(q)。考虑数学归纳法（强归纳），假设结论对 n<pq 成立，那么：

所以积性函数和卷积运算同样构成交换群。

可以证明卷积对加法有分配律：f*h+g*h=(f+g)*h。

对于积性函数 f,g 和完全积性函数 h，容易证明乘法对卷积也有类似的分配律 (fh)*(gh)=(f*g)h（注意顺序和前面是反的）。这个性质有的时候可以节省大量计算贝尔级数的时间（甚至有时候没办法用贝尔级数做，比如例 7.1）。

1.3 常见数论函数

很多是基于狄利克雷卷积定义的。另外容易发现前面的单位元 \varepsilon(n) 是个完全积性函数。

一些加性函数：

• 不同质因子个数：\omega(n)（作用和名字相同）
• 质因子个数：\Omega(n)（同上，完全加性）
• 对数函数：\log n（完全加性，从这里可以看出数论函数的值域并不一定是整数）

一些积性函数：

• 常数函数：\mathbf 1(n)=1（完全积性）
• 恒等函数：\mathrm{id}(n)=n（完全积性）
• 幂函数：\mathrm{id}_k(n)=n^k（因此 \mathrm{id} 就是 \mathrm{id}_1）（完全积性）
• 约数个数：\mathrm d=\mathbf 1*\mathbf 1（作用和名字相同）
• 约数和：\sigma=\mathrm{id}*\mathbf 1（同上）
• 约数函数：\sigma_k=\mathrm{id}_k*\mathbf 1：计算每个因子的 k 次方和（因此 \mathrm d 和 \sigma 就相当于 \sigma_0 和 \sigma_1）
• 欧拉函数\text{(Euler}^{[2]}\text{'s totient}^{[3]}\text{ function)}：\varphi(n) 为 [1..n] 中与 n 互质的整数个数。另外一种定义是 \varphi=\operatorname{id}/1，两种定义之间的互相转换都很容易。
• 莫比乌斯函数\text{(Möbius}^{[4]}\text{ function)}：\mu=\mathbf 1^{-1}
• 最大公约数：\gcd(n,k)（k 为定值）
• 判断互质：\chi_k(n)=[n \perp k]=[\gcd(n,k)=1]（注意虽然 \gcd 不是完全积性但是这个是的）。用 \chi 是因为它其实是模 k 下的狄利克雷主特征\text{(Dirichlet principal character)}^{[5]}。
• 刘维尔函数\text{(Liouville}^{[6]}\text{ function)}：\lambda(n)=(-1)^{\Omega(n)}（完全积性）

另外定义差分 \Delta f(n)=f(n)-f(n-1) 和前缀和 \Sigma f(n)=\displaystyle\sum_{k=1}^nf(k)（沿用随机说话（一）的记号，和有限微积分符号不同），那么几个前缀和函数有特殊符号：

• 欧拉函数前缀和：\Phi=\Sigma\varphi
• 梅滕斯函数\text{(Mertens}^{[7]}\text{ function)}（莫比乌斯函数前缀和）：\mathrm M=\Sigma\mu（一般用大写拉丁字母 Mm (em) 而不是希腊字母 Μμ (μῦ)）

容易发现一些平凡的前缀和关系，比如 \Sigma\varepsilon=\mathbf 1,\Sigma \mathbf 1=\mathrm{id} 之类。

1.4 狄利克雷级数

众所周知普通生成函数乘法对应一般卷积，指数生成函数乘法对应二项卷积，那么有什么生成函数的乘法对应狄利克雷卷积吗？

可以想到 a^ma^n=a^{m+n} 对应加法，那么 a^nb^n=(ab)^n 对应乘法，考虑把变量 x 放到指数上。定义数论函数 f 的狄利克雷级数\text{(Dirichlet series)}或者狄利克雷生成函数\text{(Dirichlet generating function, DGF)}为：

容易证明 DGF 乘积对应 f 的狄利克雷卷积。

当 f 为积性函数时有欧拉乘积\text{(Euler product)}公式：

（\mathbb P 表示质数集合）

证明根据唯一分解定理是显然的（仅仅是形式上，实际上需要考虑收敛性问题，但是我们这里基本不会用到解析性质所以不去讨论）。

常数函数 \mathbf 1 的 DGF 是黎曼 ζ 函数\text{(Riemann}^{[8]}\text{ zeta function)}：

一些函数可以根据定义求出，比如 \varepsilon 的 DGF 就是 1，\mathrm{id} 的 DGF 是 \displaystyle\sum_{k \ge 1}\dfrac{k}{k^x}=\sum_{k \ge 1}\dfrac{1}{k^{x-1}}=\zeta(x-1)（类似方法可以得到 \mathrm{id}_k 的 DGF 是 \zeta(x-k)）。

所以对于积性函数，只要处理乘积里面的内容就行。比如说对于莫比乌斯函数，我们有：

而欧拉函数 \varphi=\mathrm{id}/\mathbf 1 的 DGF 就是 \dfrac{\zeta(x-1)}{\zeta(x)}。

用 DGF 确实可以得到积性函数之间的卷积关系，但是有种杀鸡用牛刀的感觉，有一种更简单的工具：贝尔级数。

1.5 贝尔级数

研究狄利克雷级数的经验告诉我们，积性函数重要的是它在质数幂处的值。现在考虑两个积性函数的卷积：

可以发现乘法卷积转化成了普通的加法卷积！按照这个思路，就有了贝尔级数\text{(Bell}^{[9]}\text{ series)}：

这里把 f 的贝尔级数 F_p 记作 \mathcal Bf，这样 \mathcal B(f*g)=\mathcal Bf \times \mathcal Bg（可以发现这个式子长得很像群同态）。我们暂且把 \mathcal B 称为贝尔变换。

在处理时一般只考虑 x，而把 p 当成一个常数（这就是为什么写 F_p(x) 而不是 F(p,x)）。

很容易得出一些常见函数的贝尔级数：

• \varepsilon$：$1
• \mathbf 1$：$(1-x)^{-1}
• \mathrm{id}$：$(1-px)^{-1}
• \mathrm{id}_k$：$(1-p^kx)^{-1}
• \mathrm d$：$(1-x)^{-2}
• \sigma_k$：$((1-p^kx)(1-x))^{-1}
• \varphi$：$\dfrac{1-x}{1-px}
• \mu$：$1-x

（以下为代数内容，与本文主题基本无关，可以跳过）

记 F_p \coloneqq \mathbb C^{\mathbb P} 为 \mathbb P \to \mathbb C 的函数集合，那么贝尔级数可以看成是 F_p 为系数且常数项为 1（常值函数）的形式幂级数，我们记作 B \coloneqq 1+xF_p[x]。容易验证 B 关于乘法构成一个交换群，这里记作 B^\times。

于是可以发现，贝尔变换恰好建立起了积性函数的卷积的代数对象到群 B^\times 之间的一个同态对应。并且 B 中任意一个级数都可以用类似方式还原成一个积性函数，因此它其实是一个同构！于是积性函数关于卷积构成交换群，因而继承了交换群的各种性质，比如结合律、交换律以及之前提到过的逆元存在性。

1.6 欧拉函数

这里提一下从欧拉函数的第一种定义得到卷积的方式。

首先假如你有 \dfrac{1}{n} 到 \dfrac{n}{n} 的分母为 n 的分数。以 n=12 为例：

现在对每个分数进行约分：

由于约分后的分母一定是 n 的因子，并且以每个 n 的因子为分母的最简分数一定都出现在序列里。所以：

也就是 \varphi*\mathbf 1=\mathrm{id}。反向的推导会在后面叙述。

根据狄利克雷/贝尔级数都可以得出 \varphi(p^k) 的表达式（直接根据定义理解也很容易）：

那么可以得到 \varphi(n) 关于 n 的质因子的表达式。设 n=\displaystyle\prod_{i}p_i^{k_i}，那么有：

又因为 p^k-p^{k-1}=\dfrac{p-1}{p}p^k，所以有另外一个表达式：

1.7 莫比乌斯函数

根据 DGF 或者贝尔级数都能得出 \mu(p^k) 的表达式：

所以：

即 \mu(n) 当 n 含平方因子时为 0，否则等于 \lambda(n)。因此我们可以用 \mu^2(n) 判断 n 是否含平方因子。

这样对 \mu*\mathbf 1=\varepsilon 就有另一种理解。先来介绍一个前置问题：

例 1.3 给定集合 \mathbf S，求 \displaystyle\sum_{\mathbf T \subseteq \mathbf S}(-1)^{|\mathbf T|}。

一种方法是枚举 |\mathbf T|，这样答案就是 \displaystyle\sum_{k=0}^{|\mathbf S|}\dbinom{|\mathbf S|}{k}(-1)^k=(1-1)^{|\mathbf S|}=0^{|\mathbf S|}=[|\mathbf S|=0]=[\mathbf S=\varnothing]。

另一种方法是枚举 \mathbf S 的每个元素是否选取，答案 \displaystyle\sum_{q_1,q_2,\cdots,q_{|\mathbf S|} \in \{0,1\}}(-1)^{q_1+q_2+\cdots+q_{|\mathbf S|}}=\displaystyle\sum_{q_1,q_2,\cdots,q_{|\mathbf S|} \in \{0,1\}}(-1)^{q_1}(-1)^{q_2}\cdots(-1)^{q_{|\mathbf S|}}=\sum_{q_1=0}^1(-1)^{q_1}\sum_{q_2=0}^1(-1)^{q_2}\cdots\sum_{q_{|\mathbf S|}=0}^1(-1)^{q_{|\mathbf S|}}=0^{|\mathbf S|}=[|\mathbf S|=0]=[\mathbf S=\varnothing]。这种方法容易理解一些（实际上也给二项式定理带来了一个组合证明）。

回到原来问题，设 n=p_1^{k_1}p_2^{k_2}\cdots p_v^{k_v}，\mu(d) 当 d 含平方因子时为 0，所以每项次数都是 0 或 1 时才会影响答案，答案就是 [v=0] 即 [n=1]。

由于 \mu=\mathbf 1^{-1}，因此 f/\mathbf 1=f*\mu，这样有经典的莫比乌斯反演公式\text{(Möbius inversion formula)}：

虽然一般在 OI 中听到莫比乌斯反演这个词是在 \gcd 求和中，但是实际上 \gcd 求和用不到这个定理本身。这是因为那种凑 f 和 g 的方法早就不流行了，下面介绍的是现在普遍使用的方法。

\frak{Pars\ B} \gcd 求和

\text{Chapter 2} 一维 \gcd 求和

2.1 一个简单的问题

例 2.1 求 \displaystyle\sum_{k=1}^n\mathrm d(\gcd(n,k))。

你可能会说这不简单吗，n 和 k 的最大公因子的因子数就是 n 和 k 的公因子数，枚举每一个因子算一下不就行了。

现在分析一下刚才的过程。上面这句话实际上蕴涵了一个式子：d \mid \gcd(x,y) \iff d \mid x \land d \mid y。从这一步出发推导一下：

2.2 进阶

例 2.2 求 \displaystyle\sum_{k=1}^n[\gcd(n,k)=1]。

这个就是欧拉函数的定义。

仿照前面的经验，尝试把带 \gcd 的式子拆成一个枚举约数的和式（也就是写成一个函数与 \mathbf 1 的卷积）。很容易想到因为 \mu=\mathbf 1^{-1} 所以 \mu*\mathbf 1=\varepsilon，那么：