杜教筛
杜教筛一般用于求一类数论函数的前缀和。
假设要求数论函数 \(f(x)\) 的前缀和 \(S(n) = \sum_{i=1}^n f(i)\) 。
杜教筛的关键在于构造两个合适的函数 \(g, h\) 满足 \(h = f \cdot g\) 。
这里的函数相乘指的是狄利克雷卷积。
理论
则由 \(h = f \cdot g\) 可得（以下除号表示整除）：
\[ \begin{equation} \begin{aligned} \sum_{i=1}^n h(i) &= \sum_{i=1}^n\sum_{d|i}f(\frac{i}{d})g(d) \\\\ &= \sum_{d=1}^ng(d)\sum_{i=d}^nf(\frac{i}{d})[i|d] \\\\ &= \sum_{d=1}^ng(d)\sum_{i=1}^{n/d}f(i) \\\\ &= \sum_{d=1}^ng(d)S(\frac{n}{d}) \\\\ &= g(1)S(n) + \sum_{d=2}^ng(d)S(\frac{n}{d}) \\\\ \end{aligned} \end{equation} \]
所以 \(S(n) = \sum_{i=1}^n h(i) - \sum_{d=2}^n g(d)S(\frac{n}{d})\) 。
前提是每个 \(\sum_{i=1}^n h(i)\)
很容易求，那么接下来不考虑 \(h\)
，
对于后面的部分可以整除分块，还需要快速求出 \(g\) 的一段区间和，
然后就可以递推，由于形如 \(\lfloor\frac{n}{d}\rfloor\) 的数只有 \(O(\sqrt{n})\) 个，
可以只递推这 \(O(\sqrt{n})\) 个 \(S\) ，不考虑 \(g,
h\) 的计算复杂度，复杂度为 \(O(n^{\frac{2}{3}})\) 。
update: 根据 16 年的集训队论文，直接计算的复杂度是 \(O(n^{\frac{3}{4}})\) ，
要保证复杂度的话需要线性筛预处理 \(n^{\frac{2}{3}}\) 以内的 \(S\) 。
证明后面有提到。
关于如何存储 \(S\)
，直接用数组存需要 \(O(n)\) 的空间，开
map 每次取用带一个 log ，
普通的离散化也会带一个 log 。
观察 \(\frac{n}{d}\) 的分布，当
\(d \leq \sqrt{n}\) 时， \(\frac{n}{d}\) 的值两两不同。
而当 \(d > \sqrt{n}\) 时， \(\frac{n}{d}\) 的值都不超过 \(\sqrt{n}\) 。
设 \(m\) 是 \(\frac{n}{d}\)
的不同取值个数，那么可以用如下的函数对 \(x =
\frac{n}{d}\) 进行离散化：
1 | inline int id(int x) { |
实践
举个简单的栗子：求 \(\mu\) 的前缀和。
首先根据 \(\mu\) 的性质不难想到 \(\mu \cdot I = \epsilon\) 。
那么就将 \(f = \mu, g = I, h = \epsilon\) 代入上去，得到：
\[S(n) = \sum_{i=1}^n \mu(i) = \sum_{i=1}^n \epsilon(i) - \sum_{d=2}^n I(d) \cdot S(\frac{n}{d})\]
即
\[S(n) = 1 - \sum_{d=2}^n S(\frac{n}{d})\]
扩展
但有时候无法构造合适的 \(h = f \cdot
g\) 使得 \(g, h\) 的前缀和可以
\(O(1)\) 算出。
这时候杜教筛是否就毫无用武之地呢？不见得。
观察递推式，利用整除分块，设 \(S_f, S_g, S_h\) 分别表示 \(f, g, h\) 的前缀和，那么：
\[S_f(n) = S_h(n) - \sum_{i=2}^m (S_g(r_i) - S_g(r_{i-1})) S_f(\frac{n}{r_i})\]
其中 \(m\) 是 \(\frac{n}{d}\) 的不同取值个数， \(r_i\) 是整除分块后对应第 \(i\) 块的右端点。
首先不难发现需要用到的 \(S_h\)
也都是形如 \(\frac{n}{d}\) 的数，
那么只需要如果 \(S_h\)
能够杜教筛（或者其他筛）筛出来就行了。
再考虑 \(S_g\)
需要的取值，由整除分块中的 \(r = n / (n /
l)\) 可知，\(r_i\)
的取值也都是形如 \(\frac{n}{d}\)
的数，
同理只要能筛 \(S_g\) 就行了，不一定要
\(O(1)\) 算。
复杂度
发现之前对杜教筛的复杂度理解有问题。
假设已经预处理（或者可以 \(O(1)\)
计算）需要的 \(S_g, S_h\) ，
那么需要计算的 \(S(\frac{n}{d})\) 有
\(O(\sqrt{n})\) 个。
将他们分为两类：
- \(d \leq \sqrt{n}\): 这部分有 \(\sqrt{n}\) 个。
- \(d \geq \sqrt{n}, \frac{n}{d} \leq \sqrt{n}\): 这部分同样有 \(\sqrt{n}\) 个。
计算单个 \(S(x)\) 需要枚举 \(\frac{x}{d}\) ，复杂度为 \(O(\sqrt{x})\) 。
对于两部分分别计算复杂度，总复杂度就是：
\[ \sum_{i=1}^{\sqrt{n}} O(\sqrt{i}) + \sum_{i=1}^{\sqrt{n}} O(\sqrt{\frac{n}{i}}) \]
对于前者：
\[ \sum_{i=1}^{\sqrt{n}} O(\sqrt{i}) = O(\int_{0}^{\sqrt{n}}\sqrt{x}dx) = O(n^{\frac{3}{4}}) \]
对于后者：
\[ \sum_{i=1}^{\sqrt{n}} O(\sqrt{\frac{n}{i}}) = O(\int_{0}^{\sqrt{n}}\sqrt{\frac{n}{x}}dx) = O(n^{\frac{3}{4}}) \]
如果预处理 \(k\) 以内的 \(S\) 且 \(k \geq \sqrt{n}\) ，预处理部分复杂度为 \(O(k)\) ，杜教筛部分前者也可以被预处理。
对于后者：
\[ \sum_{i=1}^{\frac{n}{k}} O(\sqrt{\frac{n}{i}}) = O(\int_{0}^{\frac{n}{k}}\sqrt{\frac{n}{x}}dx) = O(\frac{n}{\sqrt{k}}) \]
当 \(k = \frac{n}{\sqrt{k}}\)
时，总复杂度达到最优，
此时 \(k = n^{\frac{2}{3}}\) ，总复杂度
\(O(n^{\frac{2}{3}})\) 。