狄利克雷生成函数

解决数论函数的有利武器。

1. 定义

定义一个数列的狄利克雷生成函数（DGF）为：

$$\tilde F(x) = \sum_{i\geq 1} \dfrac{f_i}{i^x}$$

我们如果将 $\{f_i\}$ 看作是一个从 $\mathbb N _ +$ 到 $\mathbb Z$ 的一个函数，那么该生成函数就与一个数论函数相对应。一般来说，$f_1 = 1$。下文默认 $f_1 = 1$。

如果该函数是积性的，即满足 $\forall i\bot j, f(ij) = f(i) \times f(j)$，那么 $\tilde F(x)$ 的表达可以由质数以及质数的幂的值来表达，记作（设 $P$ 表示全体质数集合）：

$$\tilde F(x) = \prod_{p\in P}(1 + \dfrac {f(p)}{p ^ x} + \dfrac{f(p) ^ 2}{p ^ {2x}} + ...)$$

2. 狄利克雷函数的卷积

就是一个简单的定义。

定义：

$$\tilde F(x)\tilde G(x) = \sum_{ij}\dfrac {f(i)g(j)}{ij}$$

这个和 $(f * g)(x) = \sum_{d | x}f(d)g(\dfrac xd)$ 是相同的。

3. 常见函数

1）常值函数

在数论中，我们常见到 $I(x) = 1$ 的函数，即 $\{1, 1, 1, …\}$ 的数列。他的 DGF 为黎曼函数，记作 $\zeta (x)$。

常值函数显然也是积性函数，我们尝试使用质数及质数的幂的值来表达，即：

$$\tilde F(x) = \prod_{p\in P}(1 + \dfrac 1{p ^ x} + \dfrac 1{p ^ {2x}} + ...)$$

我们将质数内部的用等比数列求和展开，公比 $p^{-x}$，即为：

$$1 + \dfrac 1{p ^ x} + \dfrac 1{p ^ {2x}} + ... = \dfrac{-1}{p ^ {-x} - 1} = \dfrac 1{1 - p^{-x}}$$

那么，我们得到黎曼函数的另外的表达方式：

$$\zeta(x) = \prod_{p\in P}\dfrac 1{1 - p ^ {-x}}$$

2）标号函数

（记不得叫什么了

定义 $id(x) = x$，那么我们来探究一下 $\{1, 2, 3\dots\}$ 的 DGF。

还是根据积性函数的性质，我们可以得到：

$$\tilde F(x) = \prod_{p\in P}(1 + \dfrac{p}{p ^ x} + \dfrac{p ^ 2}{p ^ {2x}}+ \dots)$$

等比数列求和，可以得到：

$$\tilde F(x) = \prod_{p\in P}\dfrac 1{1 - p ^ {1 - x}}$$

而这个由可以表示成黎曼函数：

$$\tilde F(x) = \zeta(x - 1)$$

如果我们将这个换成 $id ^ k(x) = x ^ k$，那么答案就是：

$$\tilde F(x) = \prod_{p\in P}\dfrac 1{1 - p ^ {k - x}} = \zeta(x - k)$$

3）莫比乌斯函数

对于一般的函数，我们通常讨论在质数点的取值来得到 DGF。

$$\tilde F(x) = \prod_{p\in P}(1 + \dfrac{-1}{p ^ x}) = \prod_{p\in P}\dfrac{p ^ x - 1}{p ^ x}$$

这个怎样用黎曼函数表示呢？

发现 $\displaystyle \dfrac 1{\tilde F(x)} = \prod_{p\in P}\dfrac{p ^ x}{p ^ x - 1} = \prod_{p\in P}\dfrac 1{1 - p ^ {-x}} = \zeta(x)$，所以 $\tilde F(x) = \dfrac 1{\zeta(x)}$。

4）欧拉函数

同样，直接上式子：

$$\tilde F(x) = \prod_{p\in P}(1 + \dfrac{p - 1}{p ^ x} + \dfrac{p(p - 1)}{p ^ {2x}} + \dfrac{p ^ 2(p - 1)}{p ^ {3x}} + \dots)$$

我们直接考虑先改成封闭形式：

$$\begin{aligned} \tilde F(x) &= \prod_{p\in P}(1 + \dfrac{p}{p ^ x} + \dfrac{p ^ 2}{p ^ {2x}} + \dots - \dfrac{1}{p ^ x} (1 + \dfrac{p}{p ^ x} + ...)) \\&= \prod_{p\in P}(\dfrac 1{1 - p ^ {1 - x}} - \dfrac{p ^ {-x}}{1 - p ^ {1 - x}}) \\ &= \prod_{p\in P}\dfrac{1 - p ^ {-x}}{1 - p ^ {1 - x}} \\ &= \dfrac{\zeta(x - 1)}{\zeta(x)} \end{aligned}$$

那么，这个和 $id^0 = I$ 卷积，就可以得到：$\dfrac{\zeta(x - 1)}{\zeta(x)} * \zeta(x) = \zeta(x - 1)$。这对应着 $id(x)$。

5）约数 k 次幂

首先定义 $\sigma_0(x) = \sum_{d | x}$，表示约数个数。而 $\sigma_k(x) = \sum_{d | x}d ^ k$。这里给出 $\sigma_1(k)$ 的推导。

$$\begin{aligned} \tilde F(x) &= \prod_{p\in P}(1 + \dfrac{p ^ 2 - 1}{p ^ x(p - 1)} + \dfrac{p ^ 3 - 1}{p ^ {2x}(p - 1)} + \dots) \\ &= \prod_{p\in P}\dfrac 1{p - 1}((\dfrac{p}{p ^ {0x}} + \dfrac{p ^ 2}{p ^ x} + \dots) - (\dfrac{1}{p ^ {0x}} + \dfrac{1}{p ^ {x}} + \dots)) \\ &= \prod_{p \in P}\dfrac 1{p - 1}(\dfrac{p}{1 - p ^ {1 - x}} - \dfrac{1}{1 - p ^ {-x}}) \\ &= \prod_{p\in P}\dfrac 1{p - 1}\dfrac{p - 1}{(1 - p ^ {1 - x})(1 - p ^ {-x})} \\ &= \prod_{p\in P}\dfrac{1}{(1 - p^{-x})(1 - p^{1 - x})} \\ &= \zeta(x)\zeta(x - 1) \end{aligned}$$

而对于 $\sigma_k(x) = \sum_{d | x}d ^ k$，我们有：$\tilde F(x) = \zeta(x)\zeta(x - k)$。本处证明略去。

6）乘上 $x^k$

结论：若 $f(x)$ 的 DGF 是 $\tilde F(x)$，那么 $g(x) = f(x)\times x ^ k$ 的 DGF 是 $\tilde G(x) = \tilde F(x - k)$。这个可以通过改变质数处的取值得到。证明略去。

4. 例题

T1：简单的数学题

求 $\sum_{i = 1}^n i ^ 2\varphi(i)$，使用杜教筛。

直接使用 $\tilde F(x) = \dfrac{\zeta(x - 3)}{\zeta(x - 2)}$，那么 $f(i) * id^2(i) = id^3(i)$。直接筛就可以了。

using LL = long long;

LL get_sphi(LL n)
{
	if (n < N) return sphi[n];
	if (Sphi.find(n) != Sphi.end()) return Sphi[n];
	LL ans = sum3(n);
	for (ll l = 2, r; l <= n; l = r + 1)
	{
		r = n / (n / l);
		ans = (-(sum2(r) - sum2(l - 1)) * get_sphi(n / l) % Mod + ans + Mod) % Mod;
	}
	return Sphi[n] = ans;
}