狄利克雷生成函数与高级筛法（杜教筛、PN筛、Min_25筛）

xiezheyuan · 2025-03-29 17:49:02 · 算法·理论

前置约定

注意本文不是针对数论的入门文章，因此在阅读本文前，请确保你已经了解了下面的概念：

• 欧拉函数、莫比乌斯函数、莫比乌斯反演。
• 埃氏筛、线性筛、整除分块。

狄利克雷生成函数

狄利克雷卷积

定义两个数论函数 f,g 的狄利克雷卷积 f\ast g 为：

(f\ast g)(n)=\sum_{d\mid n} f(d)g\left(\frac{n}{d}\right)

狄利克雷卷积有以下（容易证明的）基本性质：

• 交换律 f\ast g=g\ast f。
• 结合律 f\ast (g\ast h)=(f\ast g)\ast h。
• 分配律 f\ast (g+h)=f\ast g+f\ast h。

几个常见的数论函数可以用狄利克雷卷积连接：\mu\ast 1=\epsilon,\varphi\ast 1=\mathrm{id},\mu\ast \mathrm{id}=\varphi。

狄利克雷卷积的单位元为指示函数 \epsilon(n)=[n=1]。

狄利克雷生成函数

狄利克雷生成函数是研究积性函数的好工具。

对于数论函数 f(n)，定义其的狄利克雷生成函数为：

\mathbf{F}(z)=\sum_{i\geq 1} f(i)i^{-z}

根据狄利克雷生成函数的定义，可以写出 Wolfram 代码：

DirichletGF[f_, z_] := Sum[f[n] n^(-z), {n, 1, Infinity}]

为了方便，下面我们用加粗的大写字母来表示一个函数的狄利克雷生成函数。

狄利克雷生成函数有一个重要性质：

定理：对于积性函数 f(n) 及其狄利克雷生成函数 \mathbf{F}(z)，有：

\mathbf{F}(z)=\prod_{p\in\mathbb{P}} \sum_{i\geq 0} f(p^i)p^{-iz}

证明是容易的，根据算术基本定理以及积性函数的定义，取每个数的质因数分解即可得到。

狄利克雷生成函数的卷积，对应数论函数的狄利克雷卷积：

常见数论函数的生成函数

指示函数 \epsilon(n)=[n=1]。它的狄利克雷生成函数为：

常数函数 1(n)=1（为了防止歧义，下面用 c(n) 代指常数函数）。它的狄利克雷生成函数为：

其中 \zeta(z) 就是著名的黎曼 zeta 函数。

幂函数 \mathrm{id}_k(z)=z^k，它的狄利克雷生成函数为：

幂函数的重要特例是恒等函数 \mathrm{id}(z)=z，它的狄利克雷生成函数为 \zeta(z-1)。

根据基本性质 \mu\ast 1=\epsilon，易得莫比乌斯函数 \mu(n) 的狄利克雷生成函数为：

根据基本性质 \mu\ast \mathrm{id}=\varphi，易得欧拉函数 \varphi(n) 的狄利克雷生成函数为：

根据除数函数的定义 \mathrm{id}_k\ast 1=\sigma_k，易得除数函数 \sigma_k(n) 的狄利克雷生成函数为：

除数函数的特例是约数个数函数 d(n)=\sigma_1(n)，它的狄利克雷生成函数为 \zeta(z)\zeta(z-1)。

整理：

我们可以用 Wolfram 语言来检验这些结果：

DirichletGF[f_, z_] := Sum[f[n] n^(-z), {n, 1, Infinity}]
DirichletGF[If[# == 1, 1, 0] &, z] (* 指示函数，期望结果 1 *)
DirichletGF[1 &, z] (* 常数函数，期望结果 Zeta[z] *)
DirichletGF[#^k &, z] (* 幂函数，期望结果 Zeta[-k+z] *)
DirichletGF[MoebiusMu, z] (* 莫比乌斯函数，期望结果 1/Zeta[z] *)
DirichletGF[EulerPhi, z] (* 欧拉函数，期望结果 Zeta[-1+z]/Zeta[z] *)
DirichletGF[DivisorSigma[k, #] &, z] (* 除数函数，期望结果 Zeta[z] Zeta[-k+z] *)

高级筛法

求数论函数前缀和是一个经典的问题，用线性筛法可以做到 O(n)，不过这并不是终点，高级筛法一般用于在亚线性时间复杂度内求数论函数的前缀和。

常见的高级筛法有杜教筛、Min_25 筛、洲阁筛、Powerful Number 筛等等。

杜教筛

流程

杜教筛是最基本的高级筛法，它的时间复杂度较为优秀（O(n^{2/3})），但并不是所有数论函数都可以用杜教筛求和。

假设我们要求 f(n) 的前缀和 F(n)，则需要构造两个函数 g,h 使得 f\ast g=h。

记 G,H 分别为 g,h 的前缀和，那么可以推式子：

故：

如果我们能够快速求出 G(n) 以及 H(n)，那么我们就可以通过整除分块求后面的和式（注意和式中同样涉及到 F，可以向下递归并记忆化）的方法来求出 F(n)。

可以证明这一算法的时间复杂度是 O(n^{2/3})（假设求 H(n) 的时间复杂度为 O(1)，并使用某些方法如线性筛，预处理前 O(n^{2/3}) 的函数值）。

例题

51Nod 1224 莫比乌斯函数之和：求 \mu 的前缀和。

由于 \mu\ast 1=\epsilon，而 1,\epsilon 的前缀和都是容易的，因此可以用杜教筛来做。时间复杂度 O(n^{2/3})。完整代码。

为了节省篇幅，这里只给出实现关键代码，下同：

i64 get_mu(i64 n){
    if(n <= BOUND) return mu[n];
    if(mp.count(n)) return mp[n];
    i64 ans = 1;
    for(i64 l=2,r;l<=n;l=r+1){
        r = n / (n / l);
        ans -= (r - l + 1) * get_mu(n / l);
    }
    return mp[n] = ans;
}

51Nod 1239 欧拉函数之和：求 \varphi 的前缀和。

由于 \varphi\ast 1=\mathrm{id}，而 1,\mathrm{id} 的前缀和都是容易的，因此也可以用杜教筛来做。时间复杂度 O(n^{2/3})。完整代码。

int get_phi(i64 n){
    if(n <= BOUND) return phi[n];
    if(mp.count(n)) return mp[n];
    int res = (((__int128)n * (n + 1)) >> 1) % mod;
    for(i64 l=2,r;l<=n;l=r+1){
        r = n / (n / l);
        res = Sub(res, Mul((r - l + 1) % mod, get_phi(n / l)));
    }
    return mp[n] = res;
}

HDU 5608 function：给定定义域为 \mathbb{N} 的函数 f，满足 n^2-3n+2=\sum_{d\mid n}f(d)，求 f 的前缀和。

若令 g(n)=n^2-3n+2，则题目给出的等式等价于 g=f\ast 1，这是一个可以用杜教筛来处理的形式。

由于 1 的前缀和是容易的，并且 g 的前缀和：

也是容易求出的。

唯一的难点在于如何求前 O(n^{2/3}) 的 f 的前缀和。注意到 g=f\ast 1 可以改写为 f=g\ast 1^{-1}，而 1 的狄利克雷生成函数为 \zeta(z)，它的逆 \frac{1}{\zeta(z)} 是 \mu 的生成函数。故 f=g\ast \mu，可以暴力筛求出（这个过程也被称为狄利克雷差分）。

故可以用杜教筛求 f，时间复杂度 O(n^{2/3}\log n)。完整代码

int get_f(int n){
    if(n <= BOUND) return f[n];
    if(mp.count(n)) return mp[n];
    int res = Mul(Mul(n, Add(Sub(Mul(n, n), Mul(n, 3)), 2)), inv3);
    for(int l=2,r;l<=n;l=r+1){
        r = n / (n / l);
        res = Sub(res, Mul(r - l + 1, get_f(n / l)));
    }
    return mp[n] = res;
}

P4318 完全平方数： 求第 n 小的无平方因子数。

先二分，然后变成了求 \mu^2 的前缀和。这东西有一个非常容易的基于容斥的做法，和本文无关，故不展开，这里仅给出杜教筛做法。

对于 \mu^2，它的狄利克雷生成函数是什么呢？首先 f(n)=\mu^2(n) 显然是一个积性函数，因此可以得到：

故它的狄利克雷生成函数为 \frac{\zeta(z)}{\zeta(2z)}，于是杜教筛可以构造两个函数，g,h，g 的狄利克雷生成函数为 \zeta(2z)，h 的狄利克雷生成函数为 \zeta(z)。