前置知识

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}\)

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}\)