困难通用17 分钟5,935 字

杜教筛简介

1. 这是用来解决什么问题的?

想象你是一个数学侦探,想统计从1到N(比如N=10^12,超级大)中,有多少个数的莫比乌斯函数​值为1、-1或0,或者计算所有数的欧拉函数​值加起来是多少。这种“累加”操作叫前缀和​​,记作:

Sf(n)=f(1)+f(2)+⋯+f(n)S_f(n) = f(1)+f(2)+\dots+f(n)Sf​(n)=f(1)+f(2)+⋯+f(n)

如果N很小(比如1000),我们可以一个一个算。但当N像天文数字(比如10^12)时,连最快的线性筛法都要花很长时间(因为线性筛要枚举每个数)。​杜教筛​是一种“聪明”的数学+编程技巧,它利用数论卷积和整除分块,把计算时间降到大约 O(N2/3)O(N^{2/3})O(N2/3),也就是比直接算快得多。

生活类比​​:你想统计全校所有班级的人数总和。每个班级的人数你可能要一个一个数(线性)。但如果你知道每个年级的总人数(前缀和),然后把不同年级的人数加起来,就可能快很多。杜教筛就像用已知的“年级总人数”去快速推算“全校总人数”,而不需要把每个班都数完。

2. 杜教筛的核心思想——用卷积“拆解”问题

2.1 什么是狄利克雷卷积?

两个函数 fff 和 ggg 的狄利克雷卷积​定义为:

(f∗g)(n)=∑d∣nf(d)⋅g(nd)(f * g)(n) = \sum_{d|n} f(d) \cdot g\left(\frac{n}{d}\right)(f∗g)(n)=d∣n∑​f(d)⋅g(dn​)

简单说,就是把 nnn 拆成两个因子相乘,然后分别看两个函数在这些因子上的值,再加起来。例如:

  • 如果 f=1f=1f=1(常函数),g=1g=1g=1,那么 (1∗1)(n)(1*1)(n)(1∗1)(n) 就是 nnn 的因数个数​​。
  • 如果 f=1f=1f=1,g=idg=\mathrm{id}g=id(恒等函数,id(n)=n\mathrm{id}(n)=nid(n)=n),那么 (1∗id)(n)(1*\mathrm{id})(n)(1∗id)(n) 就是 nnn 的所有因数之和。

2.2 核心公式

杜教筛的关键是:我们想求 Sf(N)S_f(N)Sf​(N),但直接求很难。于是我们构造​一个简单易求的函数 ggg,让它们的卷积 h=f∗gh = f * gh=f∗g 的前缀和很容易算出来。然后利用下面这个关系:

∑i=1Nh(i)=∑i=1Ng(i)⋅Sf(⌊Ni⌋)\sum_{i=1}^N h(i) = \sum_{i=1}^N g(i) \cdot S_f\left(\left\lfloor\frac{N}{i}\right\rfloor\right)i=1∑N​h(i)=i=1∑N​g(i)⋅Sf​(⌊iN​⌋)

这个公式怎么来的?从卷积的定义交换求和顺序:

∑i=1Nh(i)=∑i=1N∑d∣if(d)g(i/d)=∑d=1Ng(d)∑i=1⌊N/d⌋f(i)(先枚举 d=i/d 的角色)=∑d=1Ng(d)Sf(⌊Nd⌋)\begin{aligned} \sum_{i=1}^N h(i) &= \sum_{i=1}^N \sum_{d|i} f(d) g(i/d) \ &= \sum_{d=1}^N g(d) \sum_{i=1}^{\lfloor N/d \rfloor} f(i) \quad (\text{先枚举 } d = i/d \text{ 的角色}) \ &= \sum_{d=1}^N g(d) S_f\left(\left\lfloor\frac{N}{d}\right\rfloor\right) \end{aligned}i=1∑N​h(i)​=i=1∑N​d∣i∑​f(d)g(i/d)=d=1∑N​g(d)i=1∑⌊N/d⌋​f(i)(先枚举 d=i/d 的角色)=d=1∑N​g(d)Sf​(⌊dN​⌋)​

把 d=1d=1d=1 的项单独拿出来,并假设 g(1)=1g(1)=1g(1)=1(大多数积性函数都满足),得到:

∑i=1Nh(i)=Sf(N)+∑d=2Ng(d)Sf(⌊Nd⌋)\sum_{i=1}^N h(i) = S_f(N) + \sum_{d=2}^N g(d) S_f\left(\left\lfloor\frac{N}{d}\right\rfloor\right)i=1∑N​h(i)=Sf​(N)+d=2∑N​g(d)Sf​(⌊dN​⌋)

移项就得到杜教筛的核心公式​​:

Sf(N)=Sh(N)−∑d=2Ng(d)⋅Sf(⌊Nd⌋)\boxed{S_f(N) = S_h(N) - \sum_{d=2}^N g(d) \cdot S_f\left(\left\lfloor\frac{N}{d}\right\rfloor\right)}Sf​(N)=Sh​(N)−d=2∑N​g(d)⋅Sf​(⌊dN​⌋)​

这个公式右边递归地出现了 SfS_fSf​ 本身,而且 ⌊N/d⌋\lfloor N/d \rfloor⌊N/d⌋ 的值只有大约 2N2\sqrt{N}2N​ 种(整除分块)。我们只需要递归计算这些值,并配合记忆化(缓存结果),就能大大降低时间复杂度。

3. 如何选择函数 ggg?

选 ggg 就像“打配合”:要让 h=f∗gh = f * gh=f∗g 的前缀和很简单,同时 ggg 本身的前缀和也要容易算(因为公式里会用到 g(d)g(d)g(d) 的累加,我们在整除分块时需要快速求一段 ggg 的和)。

常用配对:

目标 fff 选 ggg 卷积 hhh Sh(N)S_h(N)Sh​(N) 说明
μ\muμ(莫比乌斯函数) 1 μ∗1=ε\mu * 1 = \varepsilonμ∗1=ε(单位函数,只有ε(1)=1\varepsilon(1)=1ε(1)=1) 1 因为∑i=1Nε(i)=1\sum_{i=1}^N \varepsilon(i) = 1∑i=1N​ε(i)=1
φ\varphiφ(欧拉函数) 1 φ∗1=id\varphi * 1 = \mathrm{id}φ∗1=id(恒等函数) N(N+1)/2N(N+1)/2N(N+1)/2 因为 ∑i=1Ni=N(N+1)2\sum_{i=1}^N i = \frac{N(N+1)}{2}∑i=1N​i=2N(N+1)​
id\mathrm{id}id 1 id∗1=σ\mathrm{id} * 1 = \sigmaid∗1=σ(除数之和) 需要另外求? 通常不用杜教筛,直接用公式

例1:求Möbius函数前缀和 取 f=μ,g=1f=\mu, g=1f=μ,g=1,则 h=μ∗1=εh=\mu*1=\varepsilonh=μ∗1=ε,所以 Sh(N)=1S_h(N)=1Sh​(N)=1。公式变为:

Sμ(N)=1−∑d=2N1⋅Sμ(⌊Nd⌋)=1−∑d=2NSμ(⌊Nd⌋)S_\mu(N) = 1 - \sum_{d=2}^N 1 \cdot S_\mu\left(\left\lfloor\frac{N}{d}\right\rfloor\right) = 1 - \sum_{d=2}^N S_\mu\left(\left\lfloor\frac{N}{d}\right\rfloor\right)Sμ​(N)=1−d=2∑N​1⋅Sμ​(⌊dN​⌋)=1−d=2∑N​Sμ​(⌊dN​⌋)

例2:求欧拉函数前缀和 取 f=φ,g=1f=\varphi, g=1f=φ,g=1,则 h=φ∗1=idh=\varphi*1=\mathrm{id}h=φ∗1=id,Sh(N)=N(N+1)2S_h(N)=\frac{N(N+1)}{2}Sh​(N)=2N(N+1)​。公式变为:

Sφ(N)=N(N+1)2−∑d=2NSφ(⌊Nd⌋)S_\varphi(N) = \frac{N(N+1)}{2} - \sum_{d=2}^N S_\varphi\left(\left\lfloor\frac{N}{d}\right\rfloor\right)Sφ​(N)=2N(N+1)​−d=2∑N​Sφ​(⌊dN​⌋)

4. 整除分块——把递归的层数压下来

公式里需要对 ddd 从2到N求和。但直接循环 NNN 次就太慢了。但是注意到:⌊N/d⌋\lfloor N/d \rfloor⌊N/d⌋ 随着 ddd 变化,只有大约 2N2\sqrt{N}2N​ 个不同​的值。比如 N=100N=100N=100,当 d=51d=51d=51 时 ⌊100/51⌋=1\lfloor100/51\rfloor=1⌊100/51⌋=1,当 d=100d=100d=100 时也是1,所以从51到100这一大段,商都是1。我们只需要把这一整段一起处理。

具体做法:对于当前 ddd,设 q=⌊N/d⌋q = \lfloor N/d \rfloorq=⌊N/d⌋,那么下一个不同商的起点是 ⌊N/q⌋+1\lfloor N/q \rfloor + 1⌊N/q⌋+1。在这一段内,g(d)g(d)g(d) 的和可以用前缀和快速求出(因为 ggg 的前缀和也容易算)。

生活类比​​:假设你要统计班级里每个人的数学分数。直接问每个人(循环N次)太慢。但如果分数是重复的(比如很多人考了90分),你可以先按分数分组,统计每组的人数,然后用“人数×分数”快速算出总分。整除分块就是按“商”分组。

5. 编程实现——计算莫比乌斯函数前缀和(完整代码)

我们要实现 Sμ(N)S_\mu(N)Sμ​(N)。按照以下步骤:

  1. 先用线性筛预处理前 MMM 个数的 μ\muμ 和它的前缀和(MMM 通常取 N2/3N^{2/3}N2/3 左右)。
  2. 对于大于 MMM 的 NNN,使用杜教筛递归计算,并记忆化结果。
  3. 在递归中,利用整除分块快速求和。

5.1 C++ 完整代码(动态预处理上限)

cpp
#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;

// 全局变量,用于记忆化和前缀和
unordered_map<long long, long long> memo;  // 记忆化 S_mu 的结果
vector<long long> mu_sum;                  // 预处理的前缀和(下标从0开始,mu_sum[i] = S_mu(i))
int limit;                                 // 预处理的上限

// 线性筛预处理 mu 和前缀和,直到 up_to
void precompute(int up_to) {
    vector<int> mu(up_to + 1, 0);
    vector<bool> is_composite(up_to + 1, false);
    vector<int> primes;
    mu[1] = 1;
    for (int i = 2; i <= up_to; i++) {
        if (!is_composite[i]) {
            primes.push_back(i);
            mu[i] = -1;
        }
        for (size_t j = 0; j < primes.size() && i * primes[j] <= up_to; j++) {
            int p = primes[j];
            int x = i * p;
            is_composite[x] = true;
            if (i % p == 0) {
                mu[x] = 0;      // 有平方因子
                break;
            } else {
                mu[x] = mu[i] * mu[p];
            }
        }
    }
    mu_sum.resize(up_to + 1);
    mu_sum[0] = 0;
    for (int i = 1; i <= up_to; i++) {
        mu_sum[i] = mu_sum[i-1] + mu[i];
    }
}

// 杜教筛求 S_mu(N)
long long S_mu(long long N) {
    if (N <= limit) return mu_sum[N];      // 已经预处理过了
    if (memo.count(N)) return memo[N];     // 记忆化
    long long res = 1;                     // S_h(N) = 1,因为 h = epsilon
    // 整除分块,d 从2开始
    long long d = 2;
    while (d <= N) {
        long long q = N / d;               // 商
        long long next_d = N / q + 1;      // 下一个不同的 d
        // 这一段的 d 范围是 [d, next_d-1],它们的 floor(N/d) 都是 q
        // 需要求和 g(d) = 1,所以块长度 = next_d - d
        res -= (next_d - d) * S_mu(q);
        d = next_d;
    }
    memo[N] = res;
    return res;
}

int main() {
    long long N;
    cout << "请输入 N(例如 1000000 或 10000000000): ";
    cin >> N;
    // 预处理上限取 N^(2/3),但不要超过 1e7 以防内存爆炸
    limit = (int)min((long long)1e7, (long long)pow(N, 2.0/3.0));
    if (limit < 1) limit = 1;
    precompute(limit);
    cout << "S_mu(" << N << ") = " << S_mu(N) << endl;
    return 0;
}

代码解释​​:

  • mu_sum[i] 存储了从1到i的莫比乌斯函数值之和,方便直接查表。
  • memo 是一个哈希表,缓存大N的递归结果,避免重复计算。
  • 在 S_mu 中,res 初始为1(对应 Sh(N)=1S_h(N)=1Sh​(N)=1),然后减去所有 d≥2d\ge 2d≥2 的贡献。
  • 整除分块中,next_d - d 就是这一段的长度,乘以 S_mu(q)(因为 g(d)=1g(d)=1g(d)=1)。

5.2 Python 完整代码

python
import math
import sys
sys.setrecursionlimit(10**6)   # 防止递归深度太大

memo = {}
limit = 0
mu_sum = []

def precompute(up_to):
    """线性筛预处理 mu 和前缀和到 up_to"""
    mu = [0] * (up_to + 1)
    mu[1] = 1
    primes = []
    is_composite = [False] * (up_to + 1)
    for i in range(2, up_to + 1):
        if not is_composite[i]:
            primes.append(i)
            mu[i] = -1
        for p in primes:
            if i * p > up_to:
                break
            is_composite[i * p] = True
            if i % p == 0:
                mu[i * p] = 0
                break
            else:
                mu[i * p] = mu[i] * mu[p]
    # 计算前缀和
    mu_sum.append(0)   # 下标0占位
    for i in range(1, up_to + 1):
        mu_sum.append(mu_sum[-1] + mu[i])
    return mu_sum

def S_mu(N):
    """杜教筛求莫比乌斯函数前缀和"""
    if N <= limit:
        return mu_sum[N]
    if N in memo:
        return memo[N]
    res = 1   # S_h(N) = 1
    d = 2
    while d <= N:
        q = N // d
        next_d = N // q + 1
        # 这一段的长度乘以 S_mu(q)
        res -= (next_d - d) * S_mu(q)
        d = next_d
    memo[N] = res
    return res

if __name__ == "__main__":
    N = int(input("请输入 N:"))
    # 预处理上限取 N^(2/3),但不超过 10^7
    limit = min(int(1e7), int(N ** (2/3)))
    if limit < 1:
        limit = 1
    mu_sum = precompute(limit)
    print(f"S_mu({N}) = {S_mu(N)}")

6. 常见错误与避坑指南

  1. 遗忘记忆化​​:递归时如果不把结果存起来,会陷入指数级重复计算。必须用哈希表或数组缓存。
  2. 整型溢出​​:C++ 中如果 N 很大(如 10^12),N * (N+1) 可能超过 64 位?实际上 10^12 * 10^12 会溢出,但在计算 Sh(N)S_h(N)Sh​(N) 时通常用 N * (N+1) / 2,中间结果要用 long long,且要小心除以2的顺序。更好的是用 N / 2 * (N+1) 或强制类型转换。
  3. 预处理上限选择不当​​:上限太小会导致递归太多层,效率变差;上限太大可能内存超限。经验值是 N2/3N^{2/3}N2/3 左右,不超过 1e7 通常安全。
  4. 整除分块边界错误​​:next_d = N / q + 1 要确保处理完 d 到最后 N+1 时跳出循环。注意当 q = 0 时(d > N),循环应该结束。
  5. g(1) 不等于1​​:公式中假设 g(1)=1,如果 g(1)≠1,公式要稍作修改,但大多数常用积性函数 g(1)=1。
  6. 递归深度过大​​:Python 需要设置 sys.setrecursionlimit,C++ 使用循环或迭代,但递归深度一般不会太深(因为整除分块会快速缩小参数)。

7. 用杜教筛求欧拉函数前缀和

只要把代码中的 fff 和 ggg 换一下就 OK。对于欧拉函数:

Sφ(N)=N(N+1)2−∑d=2NSφ(⌊Nd⌋)S_\varphi(N) = \frac{N(N+1)}{2} - \sum_{d=2}^N S_\varphi\left(\left\lfloor\frac{N}{d}\right\rfloor\right)Sφ​(N)=2N(N+1)​−d=2∑N​Sφ​(⌊dN​⌋)

因此 S_phi(N) 的递归函数如下(C++ 风格):

cpp
long long S_phi(long long N) {
    if (N <= limit) return phi_sum[N];
    if (memo.count(N)) return memo[N];
    long long res = N * (N + 1) / 2;   // S_h(N) = N(N+1)/2
    long long d = 2;
    while (d <= N) {
        long long q = N / d;
        long long next_d = N / q + 1;
        res -= (next_d - d) * S_phi(q);
        d = next_d;
    }
    memo[N] = res;
    return res;
}

只需要把线性筛部分改成筛 φ\varphiφ 即可。

8. 总结与相关指引

杜教筛是竞赛中处理大范围积性函数前缀和的“杀手锏”。它的核心三步:

  1. 选一个好搭档 ggg​​,使得 h=f∗gh = f * gh=f∗g 和 ggg 的前缀和都容易算。
  2. 用核心公式递归​​:Sf(N)=Sh(N)−∑d=2Ng(d)Sf(⌊N/d⌋)S_f(N) = S_h(N) - \sum_{d=2}^N g(d) S_f(\lfloor N/d \rfloor)Sf​(N)=Sh​(N)−∑d=2N​g(d)Sf​(⌊N/d⌋)。
  3. 整除分块 + 记忆化 加速递归。

掌握了杜教筛,你就能轻松应付 NNN 高达 101210^{12}1012 的前缀和问题。如果想进一步学习,可以看看以下方向:

  • 莫比乌斯反演​​:杜教筛的基石之一,用于推导很多等价关系。
  • 狄利克雷卷积​​:更多有趣的搭配(如 f=idkf = \mathrm{id}^kf=idk 与 g=μg = \mug=μ)。
  • 数论分块​​(整除分块)的更多应用,比如快速求 ∑⌊N/i⌋\sum \lfloor N/i \rfloor∑⌊N/i⌋。
  • 欧拉函数与莫比乌斯函数的性质​​:理解它们的积性有助于构造 ggg。

试一试​​:请写出杜教筛求 Sid(N)=1+2+...+NS_{id}(N) = 1+2+...+NSid​(N)=1+2+...+N 的代码?其实直接用公式,但你能用杜教筛验证公式吗?(提示:取 f=id,g=μf = \mathrm{id}, g = \muf=id,g=μ,则 h=id∗μ=φh = \mathrm{id} * \mu = \varphih=id∗μ=φ,然后 SφS_\varphiSφ​ 用杜教筛求,最后解出 SidS_{id}Sid​——有点绕,但很有趣。)

希望这篇文章能帮你打开杜教筛的大门!

同类知识点