铃悬的数学小讲堂——杜教筛
铃悬
2018-12-03 10:42:18
##### # 铃悬的数学小讲堂——杜教筛
本篇算是[【狄利克雷卷积及莫比乌斯反演】](https://lx-2003.blog.luogu.org/mobius-inversion)篇的后续 qwq。
本篇在读者掌握莫比乌斯反演与狄利克雷卷积的前提下，讲述了杜教筛算法，并伴有若干例题；另外还解释了如何利用贝尔级数更方便的使用杜教筛（要求具有一定生成函数知识）。
如果掌握莫比乌斯反演，也建议看一遍上篇博客；因为可能某些符号不太一样。
## -2.符号及规定
同上篇。为方便此处再次写出：
1. $[P]$ 是指，当 $P$ 为真时，式子的值是 $1$ ；当 $P$ 为假时，式子的值是 $0$ 。// 可以理解成， `P` 是一个 0/1 布尔值， $[P]$ 就是 `(int)P`。
2. $a\mid b$ 是指 $b$ 被 $a$ 整除，即存在一个整数 $k$ 使得 $b=ka$ ；$n\perp m$ 是指 $n$ 与 $m$ 互质（注意，$1\perp1$ 是成立的）。
3. 数论函数（见下）用小写粗体字母或普通希腊文字母（如 ${\bf f,g,h},\mu,\epsilon$ ）表示。// QAQ希腊文字母不能粗体
## -1.前备知识
至少要理解莫比乌斯反演篇中的知识（即使不知道证明）qwq。
## 0.数论分块
对于一个像 $F(n)=\sum_{i=1}^n f(i)\lfloor\frac ni\rfloor$ 这样的式子，如果我们可以 $O(1)$ 求出 $f(i)$ 的区间和，那么则可以在 $O(\sqrt n)$ 的复杂度内计算 $F(n)$ 。这依赖于以下引理：
#### 引理 0.1
> 不同的 $\lfloor\frac ni\rfloor$ 只有 $O(\sqrt n)$ 种。
证明实际上很简单：如果 $i\geq\sqrt n$，那么 $1\leq\lfloor\frac ni\rfloor\leq\sqrt n$ ，又只取整数值，自然只有 $O(\sqrt n)$ 种取值。否则 $i<\sqrt n$，但这样的 $i$ 只有 $\sqrt n$ 种，自然也只会有 $O(\sqrt n)$ 种取值。
至于如何找出每一种取值，以及确定每个值对应的 $i$ 的区间，可以参考以下代码：
```cpp
int ans = 0;
for (int i = 1, j; i <= n; i = j + 1) {
j = n / (n / i);
// j 为最大的满足 floor(n/t)=floor(n/i) 的 t
ans += (n / i) * S(i, j);
}
```
代码中 $S(a,b)$ 指 $\sum_{i=a}^n f(i)$。这段代码即可求出 $\sum_{i=1}^n f(i)\lfloor\frac ni\rfloor$。
至于代码中的注释，则是因为
$$\left\lfloor\frac nt\right\rfloor\geq\left\lfloor\frac ni\right\rfloor\iff \frac nt\geq\left\lfloor\frac ni\right\rfloor\iff t\leq\frac n{\left\lfloor\frac ni\right\rfloor}\iff t\leq\left\lfloor\frac n{\left\lfloor\frac ni\right\rfloor}\right\rfloor$$
所以 t 的最大值就是 `n/(n/i)` 。
如果求和上界是 $m$ 而不是 $n$ （$m\leq n$），那就吧循环条件写成 $i\leq m$ 并令 `j=min(m,n/(n/i))` 即可。$\sum_{i=1}^n f(i)g(\lfloor\frac ni\rfloor)$ 也可以用相同求法求。
同样的，如果求 $\sum_{i=1}^{\min(n,m)}f(i)\lfloor\frac ni\rfloor\lfloor\frac mi\rfloor$，也只需要令 `j=min(n/(n/i),m/(m/i))`，复杂度仍旧是 $O(\sqrt{\max(n,m)})$。
## 1.杜教筛
如果给定函数 $\bf f,g$，令 ${\bf S}(n)=\sum_{i=1}^n{\bf f}(i)$，则有
$$\sum_{i=1}^n({\bf f*g})(i)=\sum_{i=1}^n\sum_{xy=i}{\bf f}(x){\bf g}(y)=\sum_{y=1}^n{\bf g}(y)\sum_{xy\leq n}{\bf f}(x)=\sum_{y=1}^n{\bf g}(y){\bf S}\left(\left\lfloor\frac ny\right\rfloor\right)$$
换句话说，
$${\bf g}(1){\bf S}(n)=\sum_{i=1}^n({\bf f*g})(i)-\sum_{y=2}^n{\bf g}(y){\bf S}\left(\left\lfloor\frac ny\right\rfloor\right)$$
这是由上面的等式右侧除了 $y=1$ 一项之外都移项到左边得到的。
由此我们可以得到一个 ${\bf S}$ 的计算方法（假设 $({\bf f*g})(i)$ 的前缀和与 ${\bf g}(i)$ 的区间和都可以 $O(1)$ 计算，以下计算复杂度时亦作此假设）：
```cpp
int S(int n) {
int ans = ???; // \sum_{i=1}^n(f*g)(i)
for (int i = 2, j; i <= n; i = j + 1) {
j = n / (n / i);
ans -= Sg(i, j) * S(n / i);
}
ans /= g1;
return ans;
}
```
其中 `ans` 初值为 $\sum_{i=1}^n({\bf f*g})(i)$，${\bf Sg}(i,j)=\sum_{k=i}^j{\bf g}(k)$。
这段代码如何优化复杂度呢？首先估计计算 ${\bf S}(N)$ 的过程中产生了多少递归计算。
以下，我们以 $N$ 指最初给出的 $n$，以 $n$ 指递归调用产生的 $n$。
#### 引理1.1
> 对于任意正整数 $x,y,z$，有 $\left\lfloor\frac{\left\lfloor\frac zx\right\rfloor}y\right\rfloor=\left\lfloor\frac z{xy}\right\rfloor$
证明也很简单：假设 $z=ax+b,a=cy+d$，其中 $0\leq b<x,0\leq d<y$，那么显然 $\left\lfloor\frac zx\right\rfloor=a,\left\lfloor\frac ay\right\rfloor=c$，于是等号左边就等于 $c$。同样的，我们有 $z=cxy+(dx+b)$，其中 $0\leq dx+b\leq(y-1)x+(x-1)=xy-1<xy$，所以 $\left\lfloor\frac z{xy}\right\rfloor=c$。所以等号左右相等。
由此可以发现，上面的代码在计算 ${\bf S}(N)$ 时，产生的（直接的或间接的）递归计算中的 $n$ 都是某个 $\left\lfloor\frac Nx\right\rfloor$（因为如果这次的 $n$ 是 $\lfloor\frac nx\rfloor$，下次一定是某个 $\left\lfloor\frac{\lfloor\frac nx\rfloor}i\right\rfloor=\lfloor\frac n{xi}\rfloor$)，从而根据引理 0.1 只有 $O(\sqrt N)$ 次递归调用（如果 $n$ 相等的只计算一次的话），记忆化即可。
如果略去递归调用的复杂度，显然计算一次 ${\bf S}(n)$ 是 $O(\sqrt n)$。根据引理 0.1 的证明过程可知递归调用的 $n$ 分别为 $1,2,\dots,\sqrt N,\lfloor\frac N1\rfloor,\lfloor\frac N2\rfloor,\dots\lfloor\frac N{\sqrt N}\rfloor$。于是复杂度为
$$O\left(\sum_{i=1}^{\sqrt N}\sqrt i+\sum_{i=1}^{\sqrt N}\sqrt{\left\lfloor\frac Ni\right\rfloor}\right)=O\left(\sum_{i=1}^{\sqrt N}\sqrt{\left\lfloor\frac Ni\right\rfloor}\right)=O\left(\int_1^{\sqrt N}\sqrt{\frac Nx}{\rm d}x\right)=O\left(N^{\frac34}\right)$$
第一步等号是因为后面的求和项显然比左边的大，所以在大 $O$ 符号中左边的可以省略。第二步等号为积分近似。
但是我们不能满足于此。我们发现如果对于较小的 $n$ 仍然 $O(\sqrt n)$ 计算 ${\bf S}$ 是不明智的，因为大部分情况下我们可以 $O(n)$ 预处理出 ${\bf S}(1),{\bf S}(2),\dots{\bf S}(n)$（利用线性筛一类）。我们如果预处理出 $1\dots N^c(c>\frac12)$ 的答案，那么需要递归计算的只剩下$\lfloor\frac N1\rfloor,\lfloor\frac N2\rfloor,\dots\lfloor\frac N{N^{1-c}}\rfloor$，于是复杂度变成
$$
O\left(N^c+\sum_{i=1}^{N^{1-c}}\sqrt{\left\lfloor\frac Ni\right\rfloor}\right)=O\left(N^c+\int_1^{N^{1-c}}\sqrt{\frac Nx}{\rm d}x\right)=O\left(N^c+N^{1-\frac12 c}\right)
$$
取 $c=\frac23$ 时复杂度最优，为 $O(N^{\frac23})$。
对于记忆化：可以使用 `map`，但会导致复杂度多一个 $\log$。
更好的做法是，由于递归调用的 $n$ 总是某个 $\lfloor\frac Nx\rfloor$，并且 $x>n^{\frac13}$ 的时候都会直接查预处理的表，所以可以直接记 `Ans[x]` 表示 $\lfloor\frac Nx\rfloor$ 的答案。详细代码例题中会给出。
对于计算 $\sum_{i=1}^n({\bf f*g})(i)$，由于后面还有 $O(\sqrt n)$ 的递归复杂度，所以这个东西只要在 $O(\sqrt n)$ 时间算完就不影响杜教筛复杂度；或者因为 $n$ 都是 $\lfloor\frac Nx\rfloor$，所以这个也可以套一层杜教筛。$\sum_{i=1}^n{\bf g}(i)$ 也类似，因为要计算的 $n$ 都是某个 $\lfloor\frac Nx\rfloor$，所以这个 $\bf g$ 的前缀和也可以再套一层杜教筛qaq。
## 2.例题
### 1.[P4213 【模板】杜教筛（Sum）](https://www.luogu.org/problemnew/show/P4213)
#### Description
给定 $n\leq 2^{31}-1$，求：${\bf S}_{\varphi}(n)=\sum_{i=1}^n\varphi(n)$，以及 ${\bf S}_{\mu}(n)=\sum_{i=1}^n\mu(n)$。
### Solution
首先两个答案一定在 `long long` 和 `int` 范围内，因为 $0\leq\varphi(n)\leq n,-1\leq\mu(n)\leq1$。
杜教筛的难点在于，给定一个 ${\bf f}(n)$，要找一个合适的函数 ${\bf g}(n)$ 使 ${\bf g},{\bf f*g}$ 的前缀和都可以快速计算。
对于 $\varphi(n)$，我们知道 $\varphi=\mu*{\bf id},\varphi*{\bf 1}={\bf id}$。所以选取 ${\bf g}(n)=1$ 即可，此时 $({\bf f*g})(n)=n$，很容易求和。
对于 $\mu(n)$，选取 ${\bf g}(n)=1$ 也可，此时 $({\bf f*g})=\epsilon(n)=[n=1]$，也很容易求和。
#### Code
下面给出求 ${\bf S}_\varphi$ 的代码：
```cpp
typedef long long LL;
const int maxn = 2147483647;
const int maxm = 2000000;
LL S1[maxm], S2[1300];
bool vis[1300];
int N;
LL S(int n) {
if (n < maxm) return S1[n];
int x = N / n; // 如果存在某个 x 使得 n = floor(N / x)，
// 选 x = floor(N / n) 一定可以。
if (vis[x]) return S2[x];
vis[x] = true;
LL &ans = S2[x];
ans = (LL)n * (n + 1) / 2; // 对 (f*g)(n) = n 求和
for (int i = 2, j; i <= n; i = j + 1) {
j = n / (n / i);
ans -= (j - i + 1) * S(n / i);
}
return ans;
}
```
代码中 `maxn, maxm, 1300` 分别是 $N,N^{\frac23},N^{\frac13}$ 的最大值，`S1[i]` 在执行之前应预处理，是当 $n\leq N^{\frac23}$ 时的 ${\bf S}_\varphi(n)$。`S2[x],vis[x]` 用来记忆化 ${\bf S}_\varphi(\lfloor\frac Nx\rfloor)$。
至于代码中的第一句注释，则是因为 $\lfloor\frac Nn\rfloor$ 是使得 $xn\leq N\iff\lfloor\frac Nx\rfloor\geq n$ 的最大正整数 $x$ 。如果这个 $x$ 还不满足 $\lfloor\frac Nx\rfloor=n$ 的话，就不可能存在其他 $x$ 了。
### 2. [P3768 简单的数学题](https://www.luogu.org/problemnew/show/P3768)
#### Description
给定 $n$，求
$$\sum_{i=1}^n\sum_{j=1}^n(ij\gcd(i,j))$$
对 $p$ 取模。$n,m\leq10^{10},5\times10^8\leq p\leq1.1\times10^9$ 且 $p$ 是质数。时限 6s。
#### Solution
首先有
$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^n(ij\gcd(i,j))\\=&\sum_{i=1}^n\sum_{j=1}^n\left(ij\sum_{d\mid i,d\mid j}\varphi(d)\right)\\=&\sum_{d=1}^{n}\varphi(d)\left(\sum_{1\leq i\leq n,d\mid i}i\right)\left(\sum_{1\leq j\leq n,d\mid j}j\right)\\=&\sum_{d=1}^{n}d^2\varphi(d)S\left(\left\lfloor\frac nd\right\rfloor\right)^2\end{aligned}$$
式中 $S(k)=\sum_{i=1}^k i=\frac{k(k+1)}2$。第一步等式是因为 $\sum_{d\mid k}\varphi(d)=k$。第二步等式是交换了求和顺序，把对 $d$ 的求和放到最外层。第三步等式是把两个括号里的公因数 $d$ 提出来。
根据老套路，我们数论分块，并对每一块的 $d^2\varphi(d)$ 求区间和。
考虑使用杜教筛计算两个区间和相减。但是一个问题是时间复杂度。
假设我们已经有了函数 `LL S(LL n)` 用来求 $d^2\varphi(d)$ 的前缀和，那么接下来应该这样：
```cpp
for (int i = 1, j; i <= n && i <= m; i = j + 1) {
j = n / (n / i);
LL t = Sum(n / i);
ans = (ans + (S(j) - S(i - 1)) * t % p * t % p) % p;
}
```
可以发现 `j` 始终是某个 $\lfloor\frac nx\rfloor$ ，而 `i-1` 就是上一次的 `j` ，自然也是某个 $\lfloor\frac nx\rfloor$ 。从而恰好用到了杜教筛所有的递归计算，仍然只有 $O(n^{\frac23})$ 的复杂度。
第二个问题是对于 ${\bf f}(n)=n^2\varphi(n)$，如何找到合适的 ${\bf g}$。
考虑在数论函数的狄利克雷卷积之外定义点乘 ${\bf f\cdot g}$，指逐项相乘，即 $({\bf f\cdot g})(n)={\bf f}(n){\bf g}(n)$；定义函数 ${\bf f}(n)$ 是完全积性函数，当且仅当对于所有的 $n,m$ 都有 ${\bf f}(nm)={\bf f}(n){\bf f}(m)$。像 $\epsilon(n)=[n=1],{\bf id}^k(n)=n^k$ 都在此列。
#### 引理 2.1
> 若 ${\bf f}$ 是完全积性函数，${\bf g, h}$ 是数论函数，则 $({\bf f\cdot g})*({\bf f\cdot h})={\bf f}\cdot({\bf g*h})$。
证明是很显然的：
$$\begin{aligned}&\left(({\bf f\cdot g})*({\bf f\cdot h})\right)(n)\\=&\sum_{d\mid n}{\bf f}(d){\bf g}(d){\bf f}\left(\frac nd\right){\bf h}\left(\frac nd\right)\\=&{\bf f}(n)\sum_{d\mid n}{\bf g}(d){\bf h}\left(\frac nd\right)\\=&\left({\bf f}\cdot({\bf g*h})\right)(n)\end{aligned}$$
由此，对于 ${\bf f}(n)=n^2\varphi(n)$，即 ${\bf f}={\bf id}^2\cdot\varphi$，可取 ${\bf g}={\bf id}^2\cdot{\bf 1}$，则根据上述引理有 ${\bf f*g}={\bf id}^2\cdot(\varphi*{\bf 1})$，即 ${\bf f*g}={\bf id}^3$。
所以令 ${\bf g}(n)=n^2\cdot1=n^2$，则立得
$${\bf S}(n)=\sum_{i=1}^ni^3-\sum_{i=2}^ni^2{\bf S}\left(\left\lfloor\frac ni\right\rfloor\right)$$
至于如何对 $i^2,i^3$ 求和，我们有 $\sum_{i=1}^ni^3=\frac{n^2(n+1)^2}4$，$\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}6$。
具体代码作为练习（雾），其实和上面的 $\varphi(n)$ 的杜教筛是类似的。
### 3. BZOJ4176 Lucas的数论
这是权限题。
#### Description
给定 $n$，求 $\sum_{i=1}^n\sum_{j=1}^n{\bf d}(ij)$。${\bf d}(k)$ 是 $k$ 的约数个数。
$n\leq10^9$。简化版是[[SDOI2015]约数个数和](https://www.luogu.org/problemnew/show/P3327)。
#### Solution
对于 ${\bf d}(ij)$，考虑某个 $d\mid ij$ 来说，令 $a=\frac i{\gcd(i,d)},b=\frac d{\gcd(i,d)}$，显然 $a\perp b,a\mid i,b\mid j$ （前两个显然，最后一个是因为$b\gcd(i,d)\mid ij\Rightarrow b\mid aj\Rightarrow b\mid j$ 。最后一步是因为 $a\perp b$ ）。另外，任意给定两个数 $a,b$ 使得 $a\perp b,a\mid i,b\mid j$ 都有 $d=\frac iab\mid ij$ ，且 $\frac i{\gcd(i,d)}=a,\frac d{\gcd(i,d)}=b$。 由此可知
$$\sum_{d\mid ij}1=\sum_{a\mid i,b\mid j,a\perp b}1=\sum_{a\mid i,b\mid j}[a\perp b]$$
所以
$$\begin{aligned}ans=&\sum_{i=1}^n\sum_{j=1}^n{\bf d}(ij)\\=&\sum_{i=1}^n\sum_{j=1}^n\sum_{a\mid i}\sum_{b\mid j}[a\perp b]\\=&\sum_{i=1}^n\sum_{j=1}^n\sum_{a\mid i}\sum_{b\mid j}\sum_{d\mid a,d\mid b}\mu(d)\\=&\sum_{d=1}^n\mu(d)\left(\sum_{d\mid a}\sum_{a\mid i\leq n}1\right)\left(\sum_{d\mid b}\sum_{b\mid j\leq n}1\right)\\=&\sum_{d=1}^n\mu(d)\left(\sum_{a=1}^{\lfloor\frac nd\rfloor}\left\lfloor\frac {\lfloor\frac nd\rfloor}a\right\rfloor\right)^2\end{aligned}$$
令 $F(n)=\sum_{i=1}^n\left\lfloor\frac ni\right\rfloor=\sum_{i=1}^n\sum_{ij\leq n}1=\sum_{t=1}^n{\bf d}(t)$，
$$ans=\sum_{d=1}^n\mu(d)F\left(\left\lfloor\frac nd\right\rfloor\right)^2$$
对 $d$ 数论分块，则需要快速求出 $\mu(d)$ 的前缀和与 $F\left(\left\lfloor\frac nd\right\rfloor\right)$。前者可以直接杜教筛；后者可以借鉴杜教筛的思想。
考虑到单次计算 $F(n)$ 复杂度为 $O(\sqrt n)$（数论分块），而预处理 $F(1)\dots F(n)$ 复杂度是 $O(n)$（因为可以线性筛出 ${\bf d}$，则可以预处理出 $F(1)\dots F(n^{\frac23})$，后面的 $F$ 依次 $O(\sqrt n)$ 算，复杂度仍然是 $O(n^{\frac23})$。
虽然实际上这道题不预处理的话 $O(n^{\frac34})$ 也能过，但是无所谓了qaq。
### 4. 奇怪的题目
#### Description
给定 $n$ ，求 $\sum_{i=1}^n(\mu^2*({\bf id}\cdot\mu))(i)$。
其中 $n\leq10^9$，$\mu^2(n)=(\mu(n))^2$。
#### Solution
令 ${\bf f}=\mu^2*({\bf id}\cdot\mu)$，则 ${\bf id}*f=({\bf id}*({\bf id}\cdot\mu))*\mu^2=\mu^2$。所以取 ${\bf g}(n)=n$，因此
$${\bf S}(n)=\sum_{i=1}^n\mu^2(i)-\sum_{i=2}^ni{\bf S}\left(\left\lfloor\frac ni\right\rfloor\right)$$
剩下的就是如何计算 $\sum_{i=1}^n\mu^2(i)$。
可以发现 $\mu^2(i)=[i\text{不含平方因子}]$。所以定义 ${\bf s}(i)=\max_{d^2\mid i}d$，则 $\mu^2(i)=[{\bf s}(i)=1]$。
容易发现 $d^2\mid i\iff d\mid{\bf s}(i)$， 所以
$$\sum_{i=1}^n\mu^2(i)=\sum_{i=1}^n[{\bf s}(i)=1]=\sum_{i=1}^n\sum_{d^2\mid i}\mu(d)=\sum_{d=1}^{\lfloor\sqrt n\rfloor}\mu(d)\left\lfloor\frac n{d^2}\right\rfloor$$
可以暴力枚举 $d$，在 $O(\sqrt n)$ 时间内求出。由于杜教筛本来就有 $O(\sqrt n)$ 的计算，这并不会增加复杂度。
## 3.贝尔级数
有的时候我们不太容易找到杜教筛的合适的 ${\bf g}$，这时候有一个很厉害的东西：贝尔级数。
（Warning: 以下要求大致了解生成函数相关）
### 3.1 定义
对于积性函数 ${\bf f}(n)$ ，定义 ${\bf f}$ 模 $p$ 的贝尔级数为
$${\bf f}_p(x)=\sum_{i=0}^{\infty}{\bf f}(p^i)x^i$$
例如 $\epsilon_p(x)=1,{\bf 1}_p(x)=\frac1{1-x},{\bf id}^k_p(x)=\frac1{1-p^kx},\mu_p(x)=1-x,{\bf d}_p(x)=\frac1{(1-x)^2},\varphi_p(x)=\frac{1-x}{1-px}$。
一个很好的性质是（实际上就是把狄利克雷卷积变成了一般卷积）
$$
({\bf f*g})_p(x)={\bf f}_p(x){\bf g}_p(x)
$$
接下来我们就要生拼硬凑出一些奇怪的例题了：
### 3.2 例题
令积性函数 ${\bf f}$ 满足 ${\bf f}(p^c)=p^c+[c>0](-1)^c$，求 ${\bf f}$ 的前缀和。
可以发现 ${\bf f}_p(x)=-1+\sum_{i=0}^{\infty}\left(p^ix^i+(-1)^ix^i\right)=\frac1{1-px}+\frac1{1+x}-1$， 所以取 ${\bf g}_p(x)=(1-px)(1+x)$，即得
$$({\bf f*g})_p(x)=1+x+1-px-(1-px)(1+x)=1+px^2$$
所以问题转化成了如何求 ${\bf g}$ 的前缀和，以及如何求 ${\bf h}_p(x)=1+px^2$ 的前缀和。
显然可知 $(1-px)$ 对应 ${\bf id}\cdot\mu$，而 $(1+x)$ 对应 $\mu^2$。（指 $\mu^2(n)=(\mu(n))^2=|\mu(n)|$）。
所以 ${\bf g}=({\bf id}\cdot\mu)*\mu^2$，其前缀和可以通过之前的那道“奇怪的题目”的做法求出。
而对于 ${\bf h}(n)$ 的前缀和，可以发现只有 $n$ 是完全平方数，且每个质因数的指数都是 2 （等价于 $\mu(\sqrt n)\neq0$）时 ${\bf h}(n)=\sqrt n$，其他时候 ${\bf h}(n)=0$。所以很显然的，
$$\sum_{i=1}^n{\bf h}(i)=\sum_{i=1}^{\lfloor\sqrt n\rfloor}i\mu^2(i)$$
枚举 $i$ 即可在 $O(\sqrt n)$ 时间内算出。所以本题解决了，复杂度是 $O(n^{\frac23})$。
## 4.总结
~~本篇文章，是一位在 OI 中数学方面小有名气的选手无私的馈赠。五道杜教筛例题，涵盖了杜教筛从入门到进阶的大部分套路。你可以通过这篇文章，对杜教筛进行较为深入的了解。详细的复杂度证明、精心挑选的例题和各种不同的套路与 trick，能让你对杜教筛有一个较为全面的掌握。作者相信，这篇漂亮的博客，可以给拼搏于 OI 的逐梦之路上的你，提供一个有力的援助。~~
本文在读者已经掌握莫比乌斯反演的基础上讲述了杜教筛，并提出了若干例题，涵盖了部分杜教筛题目的套路；既可以作为杜教筛的入门文章，又可以让部分选手更进一步地了解杜教筛，更是一篇不错的杜教筛复习博客。