『学习笔记』莫比乌斯反演
对前置知识的再补充
欧拉函数：
其中一个性质：
\[n = \sum _ {d \mid n} \varphi(d).
\]
用狄利克雷卷积表示：
\[\operatorname{id} = \varphi * 1.
\]
莫比乌斯函数：
其中一个性质（或叫做定义式）：
\[\sum _ {d \mid n} \mu(d) = [n = 1].
\]
用狄利克雷卷积表示：
\[\varepsilon = \mu * 1.
\]
其中 \(1\) 函数是常函数，并且 \(1\) 函数的 DGF 就是黎曼 \(\zeta\) 函数。通过上面的补充可知，\(\mu\) 函数和常函数互为逆元。
其他函数
-
\(\sigma_0 = 1 * 1.\)
-
\(\sigma_1 = \sigma_0 * 1.\)
然后就忍不住去推测：
因为 \(\sigma_k(n) = \sum \limits _ {d \mid n} d^k\)，（好像不用推测，用 DGF 的方法就能搞出来。）
因为 \(\tilde{S_k}(x) = \tilde{I_k}(x) \times \zeta(x)\)，所以 \(\sigma_k = \operatorname{id}_ k * 1\)。
莫比乌斯反演
形式一
\[f(n) = \sum _ {d \mid n} g(d) \iff g(n) = \sum _ {d \mid n} f(d) \times \mu(\dfrac{n}{d}).
\]
证明一（卷积）：
等价于如下问题：已知 \(f = g * 1\)，求证 \(g = f * \mu\)。
因为 \(\varepsilon = \mu * 1\)，所以令等式 \(f = g * 1\) 两边同时卷 \(\mu\)，可得：
\[f * \mu = g * 1 * \mu = g * \varepsilon = g.
\]
得证。
证明二（瞎搞）：
等价于如下问题：已知 \(f(n) = \sum \limits _ {d \mid n} g(d)\)，求证 \(g(n) = \sum \limits _ {d \mid n} f(d) \times \mu(\dfrac{n}{d})\)。
\[\sum \limits _ {d \mid n} f(d) \times \mu(\dfrac{n}{d}) = \sum \limits _ {d \mid n} f(\dfrac{n}{d}) \times \mu(d)
\]
\[= \sum _ {d \mid n} \mu(d) \sum _ {k \mid \frac{n}{d}} g(k)
\]
\[= \sum _ {k \mid n} g(k) \sum _ {d \mid \frac{n}{k}} \mu(d)
\]
\[= g(n).
\]
因为 \(\sum \limits _ {d \mid \frac{n}{k}} \mu(d)\) 当且仅当 \(\dfrac{n}{k} = 1\) 时式子的值为 \(1\)，所以显然。
形式二（不常用）
\[f(n) = \sum _ {n \mid d} g(d) \iff g(n) = \sum _ {n \mid d} f(d) \times \mu(\dfrac{d}{n}).
\]
懒得证明了，感觉也挺好记的。