杜教筛

杜教筛一般用于求一类数论函数的前缀和。

假设要求数论函数 \(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
2
3
inline int id(int x) {
return x <= sqrt_of_n ? x : m - (n / x) + 1;
}

实践

举个简单的栗子:求 \(\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})\) 个。
将他们分为两类:

  1. \(d \leq \sqrt{n}\): 这部分有 \(\sqrt{n}\) 个。
  2. \(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}})\)