【学习笔记】极简的莫比乌斯反演
hanciyang
·
·
算法·理论
管理员求过，已经尽量符合书写规范了，讲解已经很清楚了。
本文章已同步到 博客园
Part 1 前置芝士
1.1 数论函数
数论函数：对于函数 f，若满足定义域为正整数，则称这个函数为 数论函数。
加性函数：对于函数 f 若满足 \gcd(p,q)=1 时 f(pq)=f(p)+f(q)，则称函数 f 为 加性函数。
积性函数：对于函数 f 若满足 \gcd(p,q)=1 时 f(pq)=f(p)f(q)，则称函数 f 为 积性函数。
若将值域扩大到任意任意正整数，仍然成立，则称为 完全加性（或积性）函数。
加性函数与积性函数均属于数论函数。
tip：\gcd(p,q)=1 指 p,q 互质。
1.2 莫比乌斯函数
根据 贝尔级数 可得：
\begin{array}{c}
\mu(p^k)=\begin{cases}1&k=0\\-1&k=1\\0&k>1\end{cases} \\
\therefore \mu(n)=\begin{cases}1&n=1\\(-1)^k&\omega(n)=\Omega(n)=k \\0&\text{otherwise}\end{cases}
\end{array}
tip：
$\text{otherwise}$ 指不满足上述条件。而上述条件中的 $p_{i}|n，\gcd(p_i,k)=1，\gcd(p_i,p_j)=1$，指对于任意 $p_i$，均属于质因数且与其他数 $p_j$ 互质，简称质因数两两互质，即质因数均不相同 。
1.3 莫比乌斯函数性质
性质 1
我们注意到，莫比乌斯函数有一个 重要性质：
\sum_{d|n}\mu(d)=[n=1]
tip：d|n 表示能被 n 整除的 d。[n=1] 指 n=1 则值为 1，否则为 0。
（口糊一下：对于所有能被 n 整除的数，它们所有的莫比乌斯函数和，当 n 等于 1 时为 1，否则为 0）。
来自百度百科的证明：
- 当 n=1 时易证。
- 当 n \ne 0 时，不妨令 n=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k}。易证：在 n 的所有因子中，莫比乌斯值不为 0 的只有质因子次数为 1 的因子，而质因子次数为 a 的因子有 C_k^r 个。\therefore \sum\limits_{d|n} \mu(n)=C_k^0 - C_k^1 + C_k^2 +...+ (-1)^k C_k^k=\sum\limits_{i=0}^k(-1)^i C_k^i
性质 2 ？
就需要用到莫比乌斯反演了。
Part 2 莫比乌斯反演
2.1 芝士：欧拉函数
直接看：
\varphi(n)=\sum_{i=1}^{n}[\gcd(n,i)=1]
可能没看懂，口糊一下，求所有不大于 n 与 n 互质的数。
那这有什么用？
再看一个重要性质：
\sum_{d|n}\varphi(n)=n
再口糊一下，所有能被 n 整除的数的欧拉函数和为 n。
来自 OI wiki 的证明：
如果 \gcd(k,n)=d，那么 \gcd(\frac{k}{d},\frac{n}{d})=1,(k<n)。
不妨设 f(x) 表示 \gcd{k,n}=x 的数的个数，那么 n=\sum\limits_{i=1}^{n}f(i)。
根据上面证明，我们注意到，f(x)=\varphi(\frac{n}{x})，从而 n=\sum\limits_{d|n}\varphi(\frac{n}{d})。再次注意到，约数 d 和 \frac{n}{d} 具有对称性，所以 n=\sum\limits_{d|n} \varphi (d)。
2.2 莫比乌斯反演及其证明
有了欧拉函数的铺垫，接下来就简单了。
还是经典直接上公式：
g(n)=\sum_{d|n} f(d)\Longleftrightarrow f(n)=\sum_{d|n}g(d)\mu \left (\frac{n}{d} \right)
啊！！！完全看不懂怎么办。g 和 f 是什么呀？
别慌，g 和 f 只是两个数论函数，并没有定义什么。其实只是如果 g(n)=\sum\limits_{d|n} f(d) 或 f(n)=\sum\limits_{d|n}g(d)\mu \left (\frac{n}{d} \right) 中的一个条件满足，那么另一个条件也满足。
不过做题目时基本用不上。
它在做题目中最经典得运用就是这个，在下面例题中也经常用到：
\sum_{p|\gcd(i,j)}\mu(p)=[\gcd(i,j)=1]
接下来要正确性证明了，这里采用喜闻乐见的推柿子大法：
g(n)=\sum_{d|n}g(d)\mu \left (\frac{n}{d} \right)=\sum_{d|n,t|\frac{n}{d}}g(t)\mu\left(\frac{n}{d}\right)=\sum_{t|n}g(t)\sum_{d|\frac{n}{d}}\mu(d)=g(n)
2.3 性质 2
现在就知道了，\sum\limits_{d|n}\frac{\mu (d)}{d} = \frac{\varphi (n)}{n}，证明也十分简单。
令 F(n)=n，f(n)=\varphi(n)，直接代入莫比乌斯反演即可。
2.4 莫比乌斯反演经典例题
Ex.1 LuoguP3455 ZAP-Queries
题意简述
对 T 组询问求 \sum\limits_{i=1}^a\sum\limits_{j=1}^b[\gcd(i,j)=d]。
数据范围：1\le d \le a,b \le 5\times10^4，T\le 5\times 10^4。
解题思路
不妨令 a\le b。约去 d 得：
\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}[\gcd(i,j)=1]
注意到，\sum\limits_{p|n}\mu(n)=[n=1] 可以变为 \sum\limits_{p|\gcd(i,j)}\mu(p)=[\gcd(i,j)=1]，代入进去，得：
\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}\sum_{p|\gcd(i,j)}\mu{(p)}
枚举 p，因为 p|\gcd(i,j)，所以 p 为 i,j 的因数，所以可得：
\sum_{p=1}^{\lfloor \frac {a}{d} \rfloor}\mu{(p)} \times {\lfloor \frac{a}{dp} \rfloor}\times{\lfloor \frac{b}{dp} \rfloor}
整除分块（数论分块）求解即可。
Ex.2 LuoguP2257 YY的GCD
题意简述
对 T 组询问求 \sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j) \in prime]。
数据范围：T=10^4，N,M\le10^7。
解题思路
我们不妨令 n\le m，k 为质数，则 k\le n
推一下柿子：
\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j) \in prime]=\sum_{k=1}^{n}\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k](k\in prime)
太史了，同时约去 k 一下，得：
\sum_{k=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[\gcd(i,j)=1](k\in prime)
注意到，\sum\limits_{d|n}\mu(d)=[n=1] 可以变为 \sum\limits_{d|\gcd(i,j)}\mu(d)=[\gcd(i,j)=1]，代入进去，得：
\sum_{k=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d|\gcd(i,j)}\mu(d)(k\in prime)
枚举 d，因为 d|\gcd(i,j)，所以 d 为 i,j 的因数，因此可得：
\sum_{k=1}^n\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\times\lfloor\frac{n}{kd}\rfloor\times\lfloor\frac{m}{kd}\rfloor(k \in prime)
这下是不是好多了，但是，别急，不妨设 T=kd，可得：
\sum_{k=1}^n\sum_{d=1}^{\lfloor \frac{n}{k}\rfloor}\mu(d)\times \lfloor
\frac{n}{T}\rfloor\times \lfloor
\frac{m}{T}\rfloor (k \in prime)
枚举 T，得：
\sum_{T=1}^n\lfloor \frac{n}{T}\rfloor\times\lfloor\frac{m}{T}\rfloor \sum_{k|T,k \in prime} \mu \left( \frac{T}{k} \right)
预处理 k，整除分块即可做出。
Ex.3 LuoguP3327 约数个数和
题意简述
设 d(x) 为 x 的约数个数，给定 T 组数据 n,m，求 \sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)。
数据范围：1\le T,n,m \le 50000。
解题思路
不难发现：
\begin{matrix}
d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1] \\
\therefore \sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1]
\end{matrix}
枚举 i 和 j，不如直接枚举 x 和 y，可得：
\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m} \lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y} \rfloor [\gcd(x,y)=1]
同样的道理：
\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m} \lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y} \rfloor \sum\limits_{d|\gcd(x,y)}\mu(d)
令 n \le m，得：
\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m} \lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y} \rfloor \sum\limits_{d=1}^n\mu(d)\times[d|\gcd(x,y)]
约去 d，得：
\sum\limits_{x=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{y=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{dx}\rfloor \lfloor \frac{m}{dy} \rfloor \sum\limits_{d=1}^n\mu(d)
再移项变好看一点，得：
\sum\limits_{d=1}^n\mu(d) \left(\sum\limits_{x=1}^{\lfloor \frac{n}{d} \rfloor}\lfloor \frac{n}{dx}\rfloor\right)\left(\sum\limits_{y=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{m}{dy} \rfloor \right)
整除分块即可。
Ex.4 LuoguP1829 Crash的数字表格
题意简述
求 \sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j) 对 20101009 取模的值。
数据范围： n,m\le 10^7 （对 20101009 取模）
解题思路
令 n\le m，不难发现：
\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)=\sum_{i=1}^n\sum_{j=1}^m\frac{i\cdot j}{\gcd(i,j)}=\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m \frac{i\times j}{d} [\gcd(i,j)=d]
约去 d，得：
\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} {i\times j\times d}[\gcd(i,j)=1]
还是同样的道理，同理可得：
\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} {i\times j\times d}\sum\limits_{k|\gcd(i,j)}\mu(k)
拆开来，再移项，得：
\sum\limits_{d=1}^nd\sum\limits_{k=1}^n\mu(k)\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}i[\gcd(k,i)=1]\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor}j[\gcd(k,j)=1]
约去 k 得：
\sum\limits_{d=1}^nd\sum\limits_{k=1}^n\mu(k)\sum\limits_{i=1}^{\lfloor \frac{n}{dk} \rfloor}ik\sum\limits_{j=1}^{\lfloor \frac{m}{dk} \rfloor}jk
太丑了，化简一下：
\sum\limits_{d=1}^nd\sum\limits_{k=1}^nk^2\mu(k)\sum\limits_{i=1}^{\lfloor \frac{n}{dk} \rfloor}i\sum\limits_{j=1}^{\lfloor \frac{m}{dk} \rfloor}j
根据等差数列求和公式：S=\frac{(a_1+a_n)\times n}{2}。再进行进一步拆开，得：
\begin{align*}
&\sum\limits_{d=1}^nd\sum\limits_{k=1}^nk^2\mu(k)\times \frac{\lfloor \frac{n}{dk} \rfloor(\lfloor \frac{n}{dk} \rfloor + 1)}{2}\times \frac{\lfloor \frac{m}{dk} \rfloor(\lfloor \frac{m}{dk} \rfloor + 1)}{2} \\
=&\sum\limits_{d=1}^nd\sum\limits_{k=1}^nk^2\mu(k)\times \frac{\lfloor \frac{n}{dk} \rfloor \lfloor \frac{m}{dk} \rfloor (\lfloor \frac{n}{dk} \rfloor + 1) (\lfloor \frac{m}{dk} \rfloor + 1)}{4}
\end{align*}
其实这样已经可以在洛谷 卡过了。但是，显然这 O(n^2) 解法还是不够优秀。
来，设 x=dk，所以可得：
\begin{array}{c}
\sum\limits_{x=1}^nx\sum\limits_{k|x}k\mu(k)\times \frac{\lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{x} \rfloor (\lfloor \frac{n}{x} \rfloor + 1) (\lfloor \frac{m}{x} \rfloor + 1)}{4}
\end{array}
令 g(x)=\sum\limits_{d|x}xd \times \mu(d)，注意到，函数 g 是一个积性函数。
\begin{align*}
\therefore g\left(\prod P_i^{a_i}\right)&=\prod g\left(P_i^{a_{i}}\right)
\\
&=\prod\left(x\times P_{i^0}\times \mu(1) +x\times P_{i}\times\mu\left(P_i\right) \right) \\
&=\prod\left((1-P_{i})x\right) \\
\end{align*}
\therefore g(p)=1-p \\
g(p^k)=g(p^{k-1}) \\
这样在满足 \gcd(n,p)=1 的情况可得：
g(np)=g(n)\times g(p)
所以我们只要预处理筛 g(T) = \sum\limits_{d \mid T} d \cdot \mu\left(\frac{T}{d}\right) 就行了。
Part 3 总结
这篇是本蒟蒻第一篇算法专栏，结合了 OI Wiki，百度百科与许多题解。其中特意没有写 狄利克雷卷积，意在更容易理解，有兴趣可以阅读。若有错误，欢迎指出。
莫比乌斯反演其实很简单，大部分只需用 \sum\limits_{p|\gcd(i,j)}\mu(p)=[\gcd(i,j)=1] 这一公式，难在推柿子。它是数论中的重要部分，希望大家能熟练掌握。