对前置知识的再补充
欧拉函数:
其中一个性质:
\[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}). \]懒得证明了,感觉也挺好记的。
标签:dfrac,limits,乌斯,sum,mid,times,mu,反演,莫比 From: https://www.cnblogs.com/Chronologika/p/17676087.html