前置知识
Part0 积性函数与完全积性函数
\(\quad\)找数学老师去......
Part1-1 莫比乌斯函数\(\mu\)
\(\quad\)首先先给出莫比乌斯函数的定义
- \(\mu_{n}=1\quad(n=1)\)
- \(\mu_{n}=(-1)^{k}\quad(n=\prod_{i=1}^{k}{p_{i}})(p_{i}互质)\)
- \(\mu_{n}=0\quad(其他情况)\)
\(\quad\)莫比乌斯函数有一个很重要的性质
- \(\sum_{d|n}\mu_{d} = [n = 1]\)
\(\quad\)我们可以使用组合数学来证明它（详见《组合数学（第五版）》Page144）
Part1-2 元函数\(\epsilon\)
\(\quad\)元函数的定义如下
- \(\epsilon_{n} = [n = 1]\)
Part1-3 不知道叫什么名字的函数\(1\)
\(\quad\)定义如下
- \(1_{n} = 1\)
Part1-4 恒等函数\(Id\)
\(\quad\)定义如下
- \(Id_n = n\)
Part2 狄利克雷卷积\(*\)
\(\quad\)我们定义两个积性函数\(f\)和\(g\)，定义
- \(f*g(n) = \sum_{d|n}f(d)*g(n/d)\)
\(\quad\)可用归纳法证明（证明略）
\(\quad\)狄利克雷卷积有以下一些性质
- \(f * g = g * f\)
- \((f * g) * h = f * (g * h)\)
- \(f * (g + h) = f * g + f * h\)
- \(f = f * \epsilon = \epsilon * f\)
Part3-1 莫比乌斯反演
\(\quad\)给出莫比乌斯反演的定义式：
- 当 \(F_n = \sum_{d|n}f_d\)
- 则有 \(f_n = \sum_{d|n}\mu_{d}*F_{n/d}\)
\(\quad\)也可以写成:
- 当\(F_n = \sum_{n|d}f_d\)
- 则有\(f_n = \sum_{n|d}\mu_{d/n}*F_d\)
Part3-2 莫比乌斯反演的证明
\(\quad\)证明如下
- 已知\(\sum_{d|n}{\mu_d} = [n = 1]\)
- 那么\(\mu * 1 = \epsilon\)
- 已知\(F_{n}=\sum_{d|n}f_{d}\)
- 那么\(F = f * 1\)
- 因为\(F * \mu = f * 1 * \mu = f * (\mu * 1)\)
- 又因为\(f * (\mu * 1) = f * \epsilon\)
- 那么\(F * \mu = f * \epsilon\)
- 又因为\(f * \epsilon = f\)
- 所以\(f = F * \mu\)
- 所以说\(f_n = \sum_{d|n}F_d*\mu_{n/d}\)
- 也就是\(f_n = \sum_{d|n}\mu_{d}*F_{n/d}\)