QwQ 文章目前没有题目，只有理论知识
狄利克雷卷积
狄利克雷卷积（Dirichlet Convolution）在解析数论中是一个非常重要的工具.
使用狄利克雷卷积可以很方便地推出一些重要函数和公式，它在信息学竞赛和解析数论中至关重要.
狄利克雷卷积是定义在数论函数间的二元运算.
数论函数，是指定义域为 \(\mathbb{N}\)（自然数），值域为 \(\mathbb{C}\)（复数） 的一类函数，每个数论函数可以视为复数的序列.
它常见的定义式为：
\[\big(f*g\big)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}{d})g(d)\quad (d\in\mathbb{N})\\\big(f*g\big)(n)=\sum_{xy=n}f(x)g(y)\quad (x,y\in\mathbb{N})\]狄利克雷卷积的一些定理
- 若 \(f\)、\(g\) 都为积性函数，那么 \(f*g\) 也为积性函数
设 \(a\)、\(b\) 满足 \(gcd(a,b)=1\)，那么：
\[\begin{aligned}& \big(f*g\big)(a)\ *\ \big(f*g\big)(b) \\=&\sum_{d_1|a}f(d_1)g(\frac{a}{d_1}) * \sum_{d_2|b}f(d_2)g(\frac{b}{d_2})\\=&\sum_{d_1d_2|ab}f(d_1d_2)g(\frac{ab}{d_1d_2})\\=&\sum_{d|ab}f(d)g(\frac{ab}{d})\\=&\big(f*g\big)(ab)\end{aligned}\]
因为满足 \(a\)、\(b\) 互质，我们能将 \(\sum_{d_1|a}\sum_{d_2|b}\) 合并成 \(\sum_{d_1d_2|ab}\)，所以 \(f*g\) 也就是积性函数了.
- 狄利克雷卷积具有交换律，即 \(f*g = g*f\)
\[\begin{aligned}&\big(f*g\big)(n)\\=&\sum_{xy=n}f(x)g(y)\\=&\sum_{yx=n}f(y)g(x)\\=&\big(g*f\big)(n)\end{aligned}\]
显而易见
- 狄利克雷卷积具有结合律，即 \((f*g)*h = f*(g*h)\)
\[\begin{aligned}&\Big(\big(f*g\big)*h\Big)(n)\\=&\sum_{wz=n}\big(f*g\big)(w)\ h(z)\\=&\sum_{wz=n}\Big(\sum_{xy=w}f(x)g(y)\Big)h(z)\\=&\sum_{xyz=n}f(x)g(y)h(z)\end{aligned}\]\[\begin{aligned}&\Big(f*\big(g*h\big)\Big)(n)\\=&\sum_{xw=n}f(x)\big(g*h\big)(w)\\=&\sum_{xw=n}f(x)\Big(\sum_{yz=w}g(y)h(z)\Big)\\=&\sum_{xyz=n}f(x)g(y)h(z)\end{aligned}\]
如上，可知两式相等，结合律成立.
- 狄利克雷卷积具有分配律，即 \((f+g)*h = (f*h)+(g*h)\)
\[\begin{aligned}&\Big(\big(f+g\big)*h\Big)(n)\\=&\sum_{xy=n}\big(f(x)+g(x)\big)\ h(y)\\=&\sum_{xy=n}f(x)h(y)+g(x)h(y)\\=&\sum_{xy=n}f(x)h(y)+\sum_{xy=n}g(x)h(y)\\=&\big(f*h\big)(n)+\big(g*h\big)(n)\end{aligned}\]
总结一下：
- 若 \(f\)、\(g\) 都为积性函数，那么 \(f*g\) 也为积性函数
- 狄利克雷卷积具有交换律，即 \(f*g = g*f\)
- 狄利克雷卷积具有结合律，即 \((f*g)*h = f*(g*h)\)
- 狄利克雷卷积具有分配律，即 \((f+g)*h = (f*h)+(g*h)\)
关于“狄利克雷卷积”名称：
首先，狄利克雷（Gustav Lejeune Dirichlet）是 19 世纪德国的数学家，他是解析数论的创立者，是解析数论很多重要理论的提出者.
“狄利克雷卷积”亦可称为“狄利克雷乘积”，如果定义普通函数加法为数论函数间的“加”运算，那么这里的狄利克雷卷积就是数论函数的“乘”运算，并且，狄利克雷卷积满足交换律、结合律和分配律，其运算法则和普通算数乘法完全类似.
函数部分（均为积性函数单位函数（单位元）\(\epsilon(n)\)\[\epsilon(n)=\begin{cases}1, && n=1 \\ 0, && \texttt{otherwise.}\end{cases}\]
显然，有：
\[\big(f*\epsilon\big)(n)=\sum_{d|n}f(d)\epsilon(\frac{n}{d})=f(n)\]
因此，单位函数 \(\epsilon(n)\) 称为狄利克雷卷积的单位元，它在狄利克雷卷积中的作用和 \(1\) 在普通乘法中的作用是类似的.
任何函数（包括 \(\epsilon\)）和 \(\epsilon\) 进行狄利克雷卷积，都得到该函数本身.
这里再引入一个东西：
狄利克雷逆
我们可以把这里的“逆”和“逆元”作类比.
例如，在普通运算中，一个数的“逆元”就是这个数的倒数；
在同余运算中，一个数的“逆元”在同个模的意义下，能使得它与这个数相乘的结果与 1 同余.
分别而言，如果我们规定 \(n\) 的逆元是 \(n^{-1}\)（这个符号是作为整体引入的，大多数情况下不能简单地理解为 \(\frac{1}{n}\)），那么就有这样两个式子：
\(n\times n^{-1} = 1\)
\(n\times n^{-1} \equiv 1 \quad \mod r\)
数字 \(1\) 代表两种运算中的单位元，所以说，逆元在类似乘法的运算中起着“倒数”的地位.
在狄利克雷卷积中，单位元为 \(\epsilon\)，我们定义狄利克雷逆如下：
\[f*f^{-1}=\epsilon\]
函数 \(f^{-1}\) 就称为函数 \(f\) 的狄利克雷逆.
幂函数 \(Id_k(n)\)\[Id_k(n)=n^k\]
特别的，有：
\(k=1\) 时，为恒等函数 \(Id(n)\)，即 \(Id(n)=n\)；
\(k=0\) 时，为常数函数 \(\pmb1(n)\)，即 \(\pmb1(n)=1\)；
这里的常数函数 \(\pmb 1(n)\) 的函数名是加粗了的数字 \(1\)，不要和 \(1\) 弄混了.
在某些场合，有人会用大写字母 \(I\) 来代替 \(\pmb 1\)，以防混淆，这里还是使用 \(\pmb 1\).
除数函数 \(\sigma_k(n)\)\[\sigma_k(n)=\sum_{d|n} d^k \quad (d\in \mathbb{N})\]
直观上理解，\(\sigma_k(n)\) 表示 \(n\) 的所有因子的 \(k\) 次幂之和.
特别的，有：
- \(k=1\) 时，为因数函数 \(\sigma(n)\)，即 \(\sigma(n)=\sum_{d|n} d\)；
- \(k=0\) 时，为个数函数 \(d(n)\)，即 \(d(n)=\sum_{d|n} 1\)；
或者说，假设 \(n\) 分解为 \(\prod_{i=1}^m p_i^{c_i} \quad (c_i\in \mathbb{N}^*, p_i\in \mathbb{P})\)，那么：
- \(\sigma(n) = \prod_{i=1}^m(\sum_{j=0}^{c_i} p_i^j)\)
- \(d(n) = \prod_{i=1}^m (c_i+1)\)
欧拉函数 \(\varphi(n)\)
在数论中，对正整数 \(n\)，欧拉函数 \(\varphi(n)\) 是小于或等于 \(n\) 的正整数中与 \(n\) 互质的数的数目。此函数以其首名研究者欧拉命名，它又称为 \(\varphi\) 函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。
当 \(n\) 是质数的时候，显然有 \(\varphi(n) = n – 1\).
一些性质
- 欧拉函数是积性函数
如果有 \(\gcd(a, b) = 1\)，那么 \(\varphi(a \times b) = \varphi(a) \times \varphi(b)\)；
特别地，当 \(n\) 是奇数时 \(\varphi(2n) = \varphi(n)\)；
- \(n = \sum_{d \mid n}{\varphi(d)}\)
可以这样考虑：如果 \(\gcd(k, n) = d\)，那么 \(\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )\)。
如果我们设 \(f(x)\) 表示 \(\gcd(k, n) = x\) 的数的个数，那么 \(n = \sum_{i = 1}^n{f(i)}\)。
根据上面的证明，我们发现，\(f(x) = \varphi(\dfrac{n}{x})\)，从而 \(n = \sum_{d|n}\varphi(\dfrac{n}{d})\)，所以上式化为 \(n = \sum_{d|n}\varphi(d)\)。
- 若 \(n = p^k\)，其中 \(p\) 是质数，那么 \(\varphi(n) = p^k – p^{k – 1}\)。
显然对于从 \(1\) 到 \(p^k\) 的所有数中，除了 \(p^{k-1}\) 个 \(p\) 的倍数以外其它数都与 \(p^k\) 互素，故 \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}\times(p-1)\)。
那么根据 1、3 性质可得：
- 若 \(n\) 的分解为 \(\prod_{i=1}^m p_i^{c_i} \quad (c_i \in \mathbb{N}^*, p_i \in \mathbb{P})\)，则 \(\varphi(n) = n\times \prod_{i=1}^m \frac{p_i-1}{p_i}\)
证明略.
欧拉定理
若 \((a,m)=1\) ，则 \(a^{\varphi(m)}\equiv1\ (\text{mod}\ m)\)
扩展欧拉定理\[a^b\equiv \begin{cases}a^{b\bmod \varphi(p)}&(a,p)=1\\a^b&(a,p)\ne 1,b<\varphi(p)\\a^{b\bmod \varphi(p)+\varphi(p)}&(a,p)\ne 1,b\geq\varphi(p)\end{cases} \mod m\]莫比乌斯函数 \(\mu(n)\) 与 莫比乌斯反演（Möbius Inversion）\[\mu(n):=\begin{cases}1&& n=1\\ 0 && n\ 含有平方因子 \\ (-1)^k && k为\ n\ 的本质不同质因子个数\end{cases}\]
或者说，若 \(n\) 的分解为 \(\prod_{i=1}^m p_i^{c_i} \quad (c_i \in \mathbb{N}^*, p_i \in \mathbb{P})\)：
若 \(n=1\)，那么 \(\mu(n)=1\)；
若 \(\exists\ i\in[1,m]\)，使得 \(c_i \ge 2\)，那么 \(\mu(n)=0\)，否则 \(\mu(n)=(-1)^m\)；
一些性质
莫比乌斯函数为积性函数；
\(\sum_{d\mid n}\mu(d)=\begin{cases}1&n=1\\0&n\neq 1\\\end{cases}\)
设 \(n=\prod_{i=1}^k{p_i}^{c_i},n’=\prod_{i=1}^k p_i\) 那么 \(\sum_{d|n}\mu(d)=\sum_{d|n’}\mu(d)=\sum_{i=0}^k \dbinom{k}{i}\cdot(-1)^i=(1+(-1))^k\)，根据二项式定理，易知该式子的值在 \(k=0\) 即 \(n=1\) 时值为 \(1\) 否则为 \(0\)，这也同时证明了 \(\sum_{d|n}\mu(d)=[n=1]=\varepsilon(n)\) 以及 \(\mu*1=\varepsilon\).
所以，莫比乌斯函数也可定义为函数 \(\pmb 1\) 的逆，即 \(\mu=\pmb 1^{-1}\)，那么就可以使用狄利克雷卷积来推导出莫比乌斯反演的结论了：
\[g=f*\pmb 1 \Leftrightarrow f=g*\mu\]
将其展开，即：
\[g(n)=\sum_{d|n}f(d)\Leftrightarrow f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})\]莫比乌斯反演扩展
对于数论函数 \(f,g\) 和完全积性函数 \(t\) 且 \(t(1)=1\):
\[f(n)=\sum_{i=1}^nt(i) g\bigg( \bigg\lfloor\frac{n}{i}\bigg\rfloor \bigg )\iff g(n)=\sum_{i=1}^n\mu(i)t(i) f\bigg( \bigg\lfloor\frac{n}{i}\bigg\rfloor \bigg )\]常用狄利克雷卷积\(\epsilon = \mu*\pmb1\)
上文：
设 \(n=\prod_{i=1}^k{p_i}^{c_i},n’=\prod_{i=1}^k p_i\) 那么 \(\sum_{d|n}\mu(d)=\sum_{d|n’}\mu(d)=\sum_{i=0}^k \dbinom{k}{i}\cdot(-1)^i=(1+(-1))^k\)，根据二项式定理，易知该式子的值在 \(k=0\) 即 \(n=1\) 时值为 \(1\) 否则为 \(0\)，这也同时证明了 \(\sum_{d|n}\mu(d)=[n=1]=\varepsilon(n)\) 以及 \(\mu*1=\varepsilon\).
\(d=\pmb1*\pmb1\)、\(\sigma = Id*\pmb1\)
均易证，略
\(Id=\varphi*\pmb1\)、\(\varphi =\mu*Id\)
上文：
\(Id(n) = n = \sum_{d \mid n}{\varphi(d)}\)
可以这样考虑：如果 \(\gcd(k, n) = d\)，那么 \(\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )\)。
如果我们设 \(f(x)\) 表示 \(\gcd(k, n) = x\) 的数的个数，那么 \(n = \sum_{i = 1}^n{f(i)}\)。
根据上面的证明，我们发现，\(f(x) = \varphi(\dfrac{n}{x})\)，从而 \(n = \sum_{d|n}\varphi(\dfrac{n}{d})\)。注意到约数 \(d\) 和 \(\dfrac{n}{d}\) 具有对称性，所以上式化为 \(n = \sum_{d|n}\varphi(d)\)。
而因为 \(\mu\) 是 \(\pmb 1\) 的逆，所以 \(\varphi*\pmb 1*\mu=Id*\mu=\varphi\)