前言
好久没更了，刚考完省选有点颓。
前置知识
- 积性函数（乘性函数）
- 数论分块
- 线性筛（欧拉筛）
- 狄利克雷卷积（Dirichlet convolution）
- 莫比乌斯反演（Möbius inversion）
概述
杜教筛用于在 $\Theta\left(n^\frac32\right)$ 的时间内求解某些函数的前缀和。
公式
杜教筛的核心公式如下：
设 $f\left(i\right)$ 为目标函数（即我们要求前缀和的函数）
设 $g\left(i\right)$ 为我们构造的一个函数。
$$g\left(1\right) \sum\limits_{i = 1}^nf\left(i\right) = \sum\limits_{i = 1}^n\left(f * g\right)\left(i\right) - \sum\limits_{i = 2}^ng\left(i\right)\sum\limits_{j = 1}^{\left\lfloor\frac nj\right\rfloor}f\left(j\right)$$
其中 $\left(f * g\right)\left(i\right)$ 为 $f\left(i\right)$ 与 $g\left(i\right)$ 的狄利克雷卷积。
如果能找到一个合适的积性函数 $g\left(x\right)$，能快速求出 $\sum\limits_{i = 1}^n\left(f * g\right)\left(i\right)$ 和 $\sum\limits_{i = l}^rg\left(i\right)$，那么就能使用数论分块递归求解了。
$f\left(i\right)$ 不一定要是积性函数。
证明
$$ g\left(1\right) \sum\limits_{i = 1}^nf\left(i\right) = \sum\limits_{i = 1}^ng\left(i\right) \sum\limits_{j = 1}^{\left\lfloor\frac ni\right\rfloor}f\left(j\right) - \sum\limits_{i = 2}^ng\left(i\right) \sum\limits_{j = 1}^{\left\lfloor\frac ni\right\rfloor}f\left(j\right) $$
$$ \begin{aligned} & \sum\limits_{d = 1}^ng\left(d\right)\sum\limits_{i = 1}^{\left\lfloor\frac nd\right\rfloor} f\left(i\right) \\ = & \sum\limits_{i = 1}^n \sum\limits_{d \mid i} f\left(d\right) g\left(\frac id\right) \\ = & \sum\limits_{i = 1}^n\left(f * g\right)\left(i\right) \end{aligned} $$
复杂度
假设算 $\sum\limits_{i = 1}^x\left(f * g\right)\left(i\right)$ 的复杂度为 $H\left(x\right)$，算 $\sum\limits_{i = 1}^xg\left(i\right)$ 的复杂度为 $G\left(x\right)$：
$$T\left(n\right) = H\left(n\right) + \sum\limits_{i = 2}^{\sqrt n} G\left(i\right) + \sum\limits_{i = 2}^{\sqrt n} T\left(\left\lfloor\frac ni\right\rfloor\right)$$
通常情况下 $H\left(N\right)$ 和 $G\left(N\right)$ 都为 $\Theta\left(1\right)$。
$$T\left(n\right) = \Theta\left(\sqrt n\right) + \sum\limits_{i = 2}^{\sqrt n} T\left(\left\lfloor\frac ni\right\rfloor\right)$$
$$T\left(\left\lfloor \frac nj\right\rfloor\right) = \mathcal O\left(\sqrt \frac nj\right) + \sum\limits_{i = 2}^{\mathcal O\left(\sqrt \frac nj\right)} T\left(\left\lfloor\frac n{ij}\right\rfloor\right)$$
后面的那个可以忽略，于是
$$T\left(\left\lfloor \frac nj\right\rfloor\right) = \mathcal O\left(\sqrt \frac nj\right)$$
$$ \begin{aligned} T\left(n\right) &= \Theta\left(\sqrt n\right) + \sum\limits_{i = 2}^{\sqrt n} T\left(\left\lfloor\frac ni\right\rfloor\right) \\ &= \Theta\left(\sqrt n\right) + \sum\limits_{i = 2}^{\sqrt n} \mathcal O\left(\sqrt\frac ni\right) \\ &= \mathcal O\left(\sum\limits_{i = 2}^{\sqrt n}\sqrt\frac ni\right) \\ &= \mathcal O\left(\int_1^{\sqrt n} \sqrt\frac ni \mathrm di\right) \\ &= \mathcal O\left(n^\frac34\right) \end{aligned} $$
众所周知的杜教筛是 $\mathcal O\left(n^\frac23\right)$ 的，原因是可以先筛出前 $m$ 个答案。复杂度变为 $\Theta\left(m\right) + \mathcal O\left(\frac n{\sqrt m}\right)$，取 $m = \Theta \left(n^\frac23\right)$ 即可。
常见函数
再看例子前，可以先看看有哪些常作为 $g\left(x\right)$ 的函数。
- $\epsilon$ 元函数。满足 $f * \epsilon = f$。$\epsilon\left(x\right) = \left[x = 1\right]$
- $\varphi$ 欧拉函数
- $I$ 恒等函数。$I\left(x\right) = 1$
- $id$ 自身函数。$id\left(x\right) = x$
- $\mu$ 莫比乌斯函数
下面 $\left(f * g\right)\left(i\right)$ 为 $f\left(i\right)$ 与 $g\left(i\right)$ 的狄利克雷卷积。
- $\mu * I = \epsilon$
- $\varphi * I = id$
- $\mu * id = \varphi$
例子
$\varphi$ 函数前缀和
由于 $\varphi * I = id$，所以取 $g = I$，那么 $f * g = id$
auto apiadu_sieve_phi = [&](auto& $, tp n) -> tp {
if (n <= m || ps_phi.count(n)) return ps_phi[n];
tp ret = n * (n + 1) / 2;
for (tp l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
ret -= (r - l + 1) * $($, n / l);
}
return ps_phi[n] = ret;
};$\mu$ 函数前缀和
由于 $\mu * I = \epsilon$，所以取 $g = I$，那么 $f * g = \epsilon$
auto apiadu_sieve_mu = [&](auto& $, tp n) -> tp {
if (n <= m || ps_mu.count(n)) return ps_mu[n];
tp ret = 1;
for (tp l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
ret -= (r - l + 1) * $($, n / l);
}
return ps_mu[n] = ret;
};$f\left(i\right) = i \times\varphi\left(i\right)$ 函数前缀和
这是一个经典例子。尽管 $f\left(i\right)$ 不再是积性函数，但我们任然可以杜教筛。
取 $g = id$，$\left(f * g\right)\left(n\right) = \sum\limits_{d \mid n} \left(\varphi\left(d\right) \cdot d\right) \cdot \frac nd = n^2$
于是我们还是可以在常数时间内计算 $\left(f * g\right)\left(i\right)$。
卡常小技巧
参考
https://www.luogu.com.cn/article/tojxbb76
https://oi-wiki.org/math/number-theory/du/
https://www.luogu.com/article/hjw4837h