Dirichlet 卷积

对于数论函数 $f(x)$ 和 $g(x)$，则定义

$$(f\ast g)(x)=\sum _{d\mid x}f(d)g\left(\frac{x}{d}\right)=\sum _{ab=x}f(a)g(b)$$

性质

Dirichlet 卷积除了满足卷积的几个性质，还有额外的性质。

卷积存在单位函数 $\epsilon (n)=[n=1]$。

卷积存在逆元 $f^{-1}$，其中 $f^{-1}(1)=0$，当 $n>1$ 时有

$$g(n)=-\frac{1}{f(1)}\sum _{d\mid n,d<n}f\left(\frac{n}{d}\right)g(d)$$

常见公式

常见的公式有

$$\begin{array}{ccc}\mu \ast 1=\epsilon & 1\ast 1=d& {\mathrm{I}\mathrm{d}}_k\ast 1={\sigma }_k\\ \phi \ast 1=\mathrm{I}\mathrm{d}& \lambda \ast 1=1_{\mathrm{S}\mathrm{q}}& d^3\ast 1=(d\ast 1{)}^2\end{array}$$

Mobius 反演

利用 $\mu \ast 1=\epsilon$，展开有

$$\sum _{d\mid n}\mu (d)=\epsilon (n)=[n=1]$$

进一步，对于数论函数 $f(n),g(n)$，有

$$\begin{array}{r}f(n)=\sum _{d\mid n}g(d)\Rightarrow g(n)=\sum _{d\mid n}\mu (d)f\left(\frac{n}{d}\right)\\ f(n)=\sum _{n\mid d}g(d)\Rightarrow g(n)=\sum _{n\mid d}\mu \left(\frac{n}{d}\right)f(d)\end{array}$$

杜教筛

对于数论函数 $f(n)$ 和它的和函数 $S(n)=\sum f(n)$，再给数论函数 $g(n)$ 的卷积求和有

$$\begin{array}{rl}\sum _{i=1}^n(f\ast g)(n)& =\sum _{i=1}^n\sum _{d=1}^{i}g(d)f\left(\frac{i}{d}\right)[d\mid i]\\ & =\sum _{d=1}^n\sum _{i=d}^{n}g(d)f\left(\frac{i}{d}\right)[d\mid i]\\ & =\sum _{d=1}^{n}g(d)\sum _{i=1}^{\lfloor n/d\rfloor }f(i)\end{array}$$

从中摘出第一项，有

$$g(1)S(n)=\sum _{i=1}^n(f\ast g)(i)-\sum _{i=2}^{n}g(i)S\left(\lfloor \frac{n}{i}\rfloor \right)$$

若前者可以快速计算，后者可以数论分块，就可以在较快的时间求得 $S(n)$。复杂度 $O(n^{\frac{3}{4}})$。

Dirichlet 级数

知道这个级数并没有什么用。。。

首先来看 Riemann $\zeta (s)$ 函数

$$\zeta (s)=\sum _{n=1}^{\mathrm{\infty }}\frac{1}{n^s}=\frac{1}{1^s}+\frac{1}{2^s}+\cdots ,\mathrm{Re}(s)>1$$

类似的，我们定义 Dirichlet 生成函数

$$DG(f;s)=\sum _{n=1}^{\mathrm{\infty }}\frac{f(n)}{n^s},\mathrm{Re}(s)>1$$

于是乘积有

$$\begin{array}{rl}DG(f;s)DG(g;s)& =\left(\sum _{n=1}^{\mathrm{\infty }}\frac{f(n)}{n^s}\right)\left(\sum _{n=1}^{\mathrm{\infty }}\frac{g(n)}{n^s}\right)\\ & =\sum _{n=1}^{\mathrm{\infty }}\left(\sum _{ab=n}\frac{f(a)}{a^s}\frac{g(b)}{b^s}\right)\\ & =\sum _{n=1}^{\mathrm{\infty }}\left(\sum _{ab=n}\frac{(f\ast g)(n)}{n^s}\right)\\ & =DG(f\ast g;s)\end{array}$$

常见的有

$$\begin{array}{rl}DG(\mu ;s)& =\sum _{n=1}^{\mathrm{\infty }}\frac{\mu (n)}{n^s}=\frac{1}{\zeta (s)}\\ DG(\phi ;s)& =\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)}{n^s}=\frac{\zeta (s-1)}{\zeta (s)}\end{array}$$