Dirichlet生成函数

数学

---

对于一些奇怪的数论问题有奇效。也是对数论函数的另一种视角。

基础形式

数列 $\left<f(1),f(2),...\right>$ 的狄利克雷生成函数是

$$F(z)=\sum_{n=1}^{\infty}\dfrac{f(n)}{n^z}$$

容易验证它的乘积就是狄利克雷卷积

$$(F*G)(z)=\sum_{n=1}\dfrac{\sum_{d|n}f(d)g(\frac{n}{d})}{n^z}$$

狄利克雷函数初看非常的诡异，它和普通型与指数型不同，并不是一个形式幂级数。我们介绍一些典型的狄利克雷生成函数来了解它的性质。

典型函数

过于显然地 $\left<1,0,0,...\right>$，也就是数论中的 $\varepsilon$ 函数，的狄利克雷生成函数是 1。

zeta 函数

众所周知研究某型生成函数都要从 $\left<1,1,...\right>$ 开始，也就是数论中的 $\mathbf{1}$ 函数，它的狄利克雷生成函数是

$$\sum_{n=1}^{\infty}\dfrac{1}{n^z}$$

你可能已经在各种科普文上见过这个函数。这就是著名的黎曼 $\zeta$ 函数。

和 $\dfrac{1}{1-x}$ 以及 $e^x$ 不同，它的性质比较复杂，我们甚至不完全了解它的零点……不过这和接下来的介绍关系不大。

$\mathbf{1}$ 是一个（完全）积性函数，把 $n$ 分解质因数后每个 $p^k$ 对它的贡献是独立的，也就是说有下面的形式

$$\prod_{p\text{ is a prime}}\sum_{k=0}^{\infty}\dfrac{f(p^k)}{p^{kz}}$$

这个形式会极大地方便我们讨论积性函数的性质。比如 $\zeta(z)=$

$$\prod_{p\text{ is a prime}}\sum_{k=0}^{\infty}\dfrac{1}{p^{kz}}$$

$$\prod_{p\text{ is a prime}}\dfrac{1}{1-p^{-z}}$$
那么它的逆就是

莫比乌斯函数

$$\prod_{p\text{ is a prime}}(1-p^{-z})$$

当 $k=0$ 时贡献为 $1$，当 $k=1$ 时贡献为 $-1$，否则贡献为 $0$，正是莫比乌斯函数 $\mu$。也就是说

$$\mu(z)=\zeta^{-1}(z)$$

ID 函数

$$\sum_{n=1}^{\infty}\dfrac{n}{n^z}$$

显然就是

$$\zeta(z-1)$$

同理，

$$\mathbf{Id}_k(z)=\zeta(z-k)$$

约数个数和

显然有

$$\sigma_k(z)=\zeta(z)\zeta(z-k)$$

欧拉函数

有

$$\varphi(z)=\dfrac{\zeta(z-1)}{\zeta(z)}$$

从中可以立刻看出欧拉函数的筛法：

$$\prod_{p\text{ is a prime}}\dfrac{1-p^{-z}}{1-p^{1-z}}$$

$$\prod_{p\text{ is a prime}}1+\sum_{k=1}^{\infty}\dfrac{(p-1)p^{k-1}}{p^{kz}}$$

也就是说，$p^k$ 的贡献是

$$\begin{cases}1&(k=0)\\(p-1)p^{k-1}&(k\ge1)\end{cases}$$

当质因数增加了一个 $p$ 的时候按这个柿子更新贡献即可。

实际应用

例一

筛出 $\varphi*\mu$。

解答

它就是 $\dfrac{\zeta(z-1)}{\zeta^2(z)}$，容易知道 $p^k$ 的贡献是

$$\begin{cases}1&(k=0)\\p-2&(k=1)\\(p^2-2p+1)p^{k-2}&(k\ge 2)\end{cases}$$

运算

我们继续来研究一下 DGF 的各种运算

下面我们讨论的 默认:

$$F(x)=\sum_{n}\frac{f(n)}{n^x}\\ G(x)=\sum_{n}\frac{g(n)}{n^x}$$

乘法

考虑:

$$F(x)\times G(x)=\sum_{n}\frac{(f*g)(x)}{n^x}$$
直接卷 可以做到 $\mathcal O(n\log n)$

高妙的高维前缀和可以做到 $\mathcal O(n\log\log n)$ 这里放板子题

求逆

事实上我们是要构造一个 $h(x)$ 满足:

$$\varepsilon(x)=(f*h)(x)=\sum_{d|x}h(d)f(\frac{x}{d})$$
按照多项式求逆的套路写:
$$h(x)=-\sum_{d|x,d \neq n} h(d)f(\frac{x}{d})$$
一样倍增处理就好了qaq

复杂度是 $\mathcal O(n\log n)$

积分和求导

先考虑求导好了 积分就是逆过程

求导的式子是:

$$(\sum_{n}\frac{f(n)}{n^s})'=\sum_{n}\frac{f(n)}{n^s}\ln n$$
我们重新定义 $\ln n$ 定义: $\ln n = n\text{的可重质因子数}$

我们记我们定义的这个函数是 $c(n)$

那么显然有 $c(xy)=c(x)+c(y)$

愉快地可以进行求导了 积分就是这个的逆过程 不多说了

取对数

直接快进到:

$$\ln F(x)=\int \frac{F'(x)}{F(x)}\operatorname{d}x$$
复杂度显然的 $\mathcal O(n\log n)$

exp

性质还好:

$$G(x)=exp(F(x))\\ G'(x)=F'(x)exp(F(x))=F'(x)G(x)\\ $$
提取系数:
$$c(n)g(n)=\sum_{d|n}c(d)f(d)g(\frac{n}{d})$$
和求逆一样倍增就好了

这堆板子看着就很好写 来一个:

void derivation(int *f,int len,int *g)
{
    for (int i = 1; i <= len; i++) g[i] = f[i] * c[i] % mod;
}
void integration(int *f,int len,int *g)
{
    g[1] = f[1];
    for (int i = 2; i <= len; i++) g[i] = f[i] * inv[c[i]] % mod;
}
void mul(int *f,int *g,int len,int *h)
{
    for (int i = 1; i <= len; i++)
        for (int j = 1; i * j <= len; j++)
            h[i * j] = (h[i * j] + f[i] * g[j]) % mod;
}
void getinv(int *f,int len,int *g)
{
    g[1] = 1;
    for (int i = 1; i <= len; i++)
        for (int j = 2; i * j <= len; j++)
            g[i * j] = (g[i * j] - g[i] * f[j] % mod + mod) % mod;
}
void getln(int *f,int len,int *g)
{
    derivation(f,len,A);
    getinv(f,len,B);
    mul(A,B,len,C);
    integration(C,len,g);
    for (int i = 1; i <= len; i++)
        A[i] = B[i] = C[i] = 0;
}
void getexp(int *f,int len,int *g)
{
    derivation(f,len,A);
    g[1] = 1;
    for (int i = 1; i <= len; i++)
    {
        if (i > 1) g[i] = g[i] * inv[c[i]] % mod;
        for (int j = 2; i * j <= len; j++)
            g[i * j] = (g[i * j] + g[i] * A[j]) % mod;
    }
    for (int i = 1; i <= len; i++)
        A[i] = 0;
}