杜教筛学习笔记

杜教筛可以利用狄利克雷卷积求任意函数的前缀和。

假设现在要求函数 $f$ 的前缀和，设 $S(n)=\sum\limits_{i=1}^n f(i)$。

接下来开始人类智慧，构造一个函数 $g$，考虑 $f$ 和 $g$ 的狄利克雷卷积的前缀和：

$\begin{aligned} &\qquad\sum\limits_{i=1}^n(f*g)(i)\\ &=\sum\limits_{i=1}^n\sum\limits_{d|i}f(i)g\left(\frac{i}{d}\right)\\ &=\sum\limits_{i=1}^ng(i)\sum\limits_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}f(j)\\ &=\sum\limits_{i=1}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ \end{aligned}$

接下来考虑：

$\begin{aligned} g(1)S(n)&=\sum\limits_{i=1}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)-\sum\limits_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ &=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ \end{aligned}$

那么只需要选取合适的函数 $g$，使得可以快速计算 $(f*g)$ 的前缀和和 $g$ 的前缀和即可递归计算出 $S(n)$。

实际问题中 $g$ 一般取 $g(x)=x,g(x)=[x=1],g(x)=1,g(x)=\mu(x),g(x)=\varphi(x)$ 等积性函数。

具体实现一般预处理尽可能多的 $S(n)$，然后递归记忆化。

具体的，当预处理 $S([1,n^{\frac{2}{3}}])$ 时递归算 $S(n)$ 的复杂度是 $O(n^{\frac{2}{3}})$ 的。

记忆化可以用哈希表，但是注意到只需要存 $S\left(\left\lfloor\frac{n}{x}\right\rfloor\right)$ 的值，而 $\left\lfloor\frac{n}{x}\right\rfloor$ 只有 $O(\sqrt n)$ 个，而 $x\le \sqrt n$ 的 $S(x)$ 一般都预处理了，所以可以直接开一个大小为 $\sqrt n$ 的数组 $a$，将 $S(x)$ 存在 $a_{\left\lfloor\frac{n}{x}\right\rfloor}$ 处。