\(\text{-1 前言}\)
\(\text{-1.0 日志}\)
24.08.24：启动本文企划，正式着笔。
\(\text{-1.1 本文记号说明}\)
本文使用 \(\cdot\) 表示乘号，\(*\) 表示卷积，\(\mathbb{P}\) 表示质数集。
\(\text{0 基础函数科技}\)
- 单位函数 \({\bf 1}(x)=1\)。
- 幂函数 \(id^k(x)=x^k\)。
- 恒等函数（幂函数的一种） \(id(x)=x\)。
- 单位元函数 \(\epsilon(x)=[x=1]\)
- 欧拉函数 \(\varphi(x)=\sum_{i=1}^x [\gcd(i,x)=1]\)
- 莫比乌斯函数 \(\mu(x)=\left\{ \begin{aligned}1, & & x=1,\\0, & & x\text{ 具有平方质因子,} \\ (-1)^k,& &k\text{为不同质因子个数.} \end{aligned}\right.\)
- 约数幂函数 \(\sigma^k(x)=\sum_{d|x}d^k\)
- 约数个数函数 \(d(x)=\sigma^0(x)=\sum_{d|x}1\)。
- 约数和函数 \(\sigma(x)=\sum_{d|x}d\)
\(\text{1 Dirichlet 卷积}\)
\(\text{1.0 定义}\)
两个数论函数 \(f(x)\) 和 \(g(x)\) 的 \(\text{Dirichlet}\) 卷积定义为：
\[h(x)=(f*g)(x)=\sum_{d|n} f(d)g\left(\frac{n}{d}\right)=\sum_{i\cdot j=n} f(i)g(j). \]后者形式通常用于证明某些命题。
\(\text{1.1 性质}\)
- 交换律：\(f*g=g*f\)，显而易见的，读者自证不难。
- 结合律：\(f*(g*h)=(f*g)*h\)。下文给出证明。
- 分配律：\((f+g)*h=f*h+g*h\)，读者自证不难。
- 两个积性函数的卷积仍是积性函数。
性质二的证明：
\[(f*(g*h))(n)=\sum_{i|n} \left(f(i) \sum_{j\left|\frac{n}{i}\right.}g(j)h\left(\frac{n}{ij}\right) \right) = \sum_{i\cdot j\cdot k=n} f(i)g(j)h(k). \]可发现任意的顺序运算最终结果均为此。
\(\text{1.2 代数结构}\)
若用 \(\mathbb{F}\) 表示数论积性函数集，则由她和 \(\text{Dirichlet}\) 卷积构成的代数结构 \((\mathbb{F},*)\) 是一个阿贝尔群。
- 封闭性：两个数论函数的 \(\text{Dirichlet}\) 卷积显然仍是一个数论函数。
- 单位元：该群的单位元是 \(\epsilon\)，即任意数论函数 \(f(x)\) 都有 \(f*\epsilon=f\)。
- 结合律：于 \(1.1\) 节已证。
- 逆元：对于一个数论积性函数 \(f\)，满足 \(f*g=\epsilon\) 的函数 \(g\) 称之为 \(f\) 的 \(Dirichlet\) 逆，记作 \(f^{-1}\)。可以证明，任意积性数论函数均有其逆元。
- 交换律：于 \(1.1\) 节已证。
莫比乌斯函数除了 \(0\) 节的第二定义以外，它的第一定义为 \(\mu=e^{-1}\)，即莫比乌斯函数是单位函数的 \(\text{Dirichlet}\) 逆。可以得到 \(\sum_{d|n}\mu(d)=[n=1]\)。
\(\text{1.3 基础函数的 Dirichlet 卷积}\)
- \(\epsilon * f=f\)。由 \(1.2\) 节已证。
- \(id * {\bf 1}=\sigma\)。证明见下文。
- \({\bf 1}*{\bf 1}=d\)。证明见下文。
- \({\bf 1} * \varphi = id\)。证明见下文。
- \(\mu*id=\varphi\)。证明见下文。
对上述第二点的证明：
\[(id*{\bf 1})(n) =\sum_{d |n}id(d){\bf 1}\left(\frac{n}{d}\right) = \sum_{d|n}d=\sigma(n). \]对上述第三点的证明：
\[({\bf 1}*{\bf 1})(n)=\sum_{d|n}{\bf 1}(d){\bf 1}\left(\frac{n}{d}\right)=\sum_{d|n}1=d(n).\]对上述第四点的证明：要证它，即证 \(\phi(n)=\sum_{d|n}\varphi(d)=n\)。
- 当 \(n=1\) 时，等式显然成立。
- 当 \(n\in \mathbb{P}\) 时，等式左边为 \(\varphi(1)+\varphi(n)=1+n-1=n\)，等式成立。
- 当 \(n=p^\alpha,p\in\mathbb{P},\alpha\in \mathbb{N^*}\) 时，等式左边等于 \(\sum_{i=0}^\alpha \varphi(p^i)=1+\sum_{i=1}^\alpha p^i-p^{i-1}=p^\alpha-p^{\alpha-1}+p^{\alpha-1}-p^{\alpha-2}+\cdots+p^1-p^0+1=p^\alpha=n\)，等式成立。
- 当 \(n=\prod_{i=1}^m p_i^{\alpha_i},p_i\in\mathbb{P},\alpha_i\in\mathbb{N^*}\) 时，由 \(\text{Dirichlet}\) 卷积的性质三，\(\phi(n)\) 也是一个积性函数，则 \(\phi(n)=\prod_{i=1}^m \phi(p_i^{\alpha_i})=\prod_{i=1}^n p_i^{\alpha_i}=n\)。
- 证毕。
对上述第五点的证明：根据第四点，等式两边同卷积 \(\mu\) 得 \(\mu * {\bf 1} * \varphi = id * \mu\)，因为 \(\mu\) 和 \(\bf 1\) 互为逆元，所以 \(\varphi = id * \mu\)，得证。
\(\text{2 莫比乌斯反演}\)
定理：对于两个数论函数 \(f(x)\)，\(g(x)\)，若 \(f(n)=\sum_{d|n} g(n)\)，则 \(g(n)=\sum_{d|n}\mu(d)f\left(\frac{n}{d}\right)\)，此时称 \(f\) 为 \(g\) 的莫比乌斯变换，\(g\) 为 \(f\) 的莫比乌斯反演。
证明：使用 \(\text{Dirichlet}\) 卷积。容易发现，\(f=g*{\bf 1}\)，所以将两边同时卷积一个莫比乌斯函数 \(\mu\)，可以得到 \(f*\mu=g*{\bf 1}*\mu\)，由于 \(\mu\) 是单位函数 \(\bf 1\) 的 \(\text{Dirichlet}\) 逆，则 \(f*\mu=g\)，得证。
\(\text{3 杜教筛}\)
杜教筛是一种用于求解积性函数前缀和的思想。
\(\text{3.0 欧拉函数前缀和}\)
定义：
\[\Phi(n)=\sum_{i=1}^n \varphi(i) \]