【学习笔记】莫比乌斯反演
Part 1 前置芝士1.1 数论函数
数论函数：对于函数 \(f\)，若满足定义域为正整数，则称这个函数为 数论函数。
加性函数：对于函数 \(f\) 若满足\(\gcd(p,q)=1(p,q \in \mathbb N^+)\) 时 \(f(pq)=f(p)+f(q)\)，则称函数 \(f\) 为 加性函数。
积性函数：对于函数 \(f\) 若满足 \(\gcd(p,q)=1(p,q \in \mathbb N^+)\) 时 \(f(pq)=f(p)f(q)\)，则称函数 \(f\) 为 积性函数。
若将值域扩大到任意 \(p,q(p,q \in \mathbb N^+)\)，仍然成立，则称为 完全加性（或积性）函数。
加性函数与积性函数均属于数论函数。
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&n=p_1p_2...p_k，p_i \ 为 \ n \ 的质因子且两两互质\\0&\text{otherwise}\end{cases}\end{array}\]
tip：\(\text{otherwise}\) 指不满足上述条件。
1.3 莫比乌斯函数性质
性质 1
我们注意到，莫比乌斯函数有一个 重要性质：
\[\sum_{d|n}\mu(d)=\]
tip：\(d|n\) 表示能被 \(n\) 整除的 \(d\)。\(\) 指 \(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}[(n,i)=1]\]
可能没看懂，口糊一下，求所有不大于 \(n\) 与 \(n\) 互质的数。
那这有什么用？
再看一个重要性质：
\[\sum_{d|n}\varphi(n)=n\]
再口糊一下，所有能被 \(n\) 整除的数的欧拉函数和为 \(n\)。
<blockquote>
来自 OI wiki 的证明：
如果 \(\gcd(k,n)=d\)，那么 \(\gcd(\frac{k}{d},\frac{n}{d})=1,(k
页:
[1]