【Coel.学习笔记】莫比乌斯反演

闲话

记得在差不多一年前写扩展欧拉定理的时候我提了一句

这周终于把古代猪文搞定了，数论这块的内容就只剩个博弈论了
别提莫比乌斯反演之类的东西，我不想搞

甚至刚开始写的时候还笔误把莫反写成了莫队……

转眼一年过去了，来填上这个大坑吧！

前言

莫比乌斯反演是一个基于莫比乌斯函数 \(\mu(n)\) 的反演算法。对于某些求和函数，如果直接求解的时间复杂度很高，而倍数或因数之和求解较为容易，则可以通过莫比乌斯反演简化运算，提高效率。

前置知识

这些前置知识可以算到莫比乌斯反演的一部分，不过也可以作为一个独立的内容（在进阶指南里其实就是这样划分的）。

莫比乌斯函数的定义

记正整数 \(x\) 的质因数分解结果为 \(x=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_n}\)（\(p_i\) 为质数且 \(\alpha_i\geq 1\)），则

\[\mu(x)=\begin{cases} 0 & \exists i,\alpha_i>1\text{（即含有平方因子）} \\ (-1)^k & \forall i,\alpha_i=1\text{ （即不含有平方因子） } \end{cases} \]

特殊地，\(\mu(1)=1\)。

莫比乌斯函数的性质

记 \(n\) 的约数的莫比乌斯函数之和 \(S_n = \sum_{d | n}\mu(d)\)，则

\[S_n=\begin{cases}1 & n=1 \\ 0 & \text{otherwise.}\end{cases} \]

\(n=1\) 显然正确，其他情况证明利用二项式定理容易得到，这里略去。

顺带一提，这个性质可以说明 \(\mu\) 在狄利克雷生成函数中为黎曼函数 \(\zeta\) 的逆元，不过对于反演没啥用（

反演定理

若对于函数 \(F(n),f(n)\)，\(F(n)=\sum_{d|n}f(d)\)，则 $$f(n)=\sum_{d|n}\mu(d)F(\dfrac{n}{d})$$

下面是证明。我们证明得到的式子左边等于右边即可：

\[\begin{aligned}\sum_{d|n}\mu(d)F(\dfrac{n}{d}) &= \sum_{d|n}\mu(d)\sum_{i|\frac{n}{d}}f(i) & \text{【代入函数 F】}\\ &=\sum_{i|n}f(i)\sum_{d|\frac{n}{i}}\mu(d)& \text{【进行数论变换】}\\ &=f(n)& \text{【利用前面提到的性质】} \end{aligned} \]

\(\text{Q.E.D.}\)

---

另一种反演定理的形式为：若 \(F(n)=\sum_{n|d}f(d)\)，则 \(f(n)=\sum_{n|d}\mu(\dfrac{d}{n})F(d)\)。

类比上一个的证明过程也不难得证：

\[\begin{aligned}\sum_{n|d}\mu(\dfrac{d}{n})F(d) &=\sum_{n|d}\mu(\dfrac{d}{n})\sum_{d|i}f(i) \\ &=\sum_{n|i}f(i)\sum_{d^\prime|\frac{i}{n}}\mu(d^\prime)\\ &= \sum_{n|i}f(i)S(\dfrac{i}{n})\\ &=f(n)\end{aligned} \]

\(\text{Q.E.D.}\)

利用这两个定理，我们可以把从 \(f(n)\) 到 \(F(n)\) 翻转过来求解，这个过程就叫做莫比乌斯反演。

例题

待补充……