杜教筛

杜教筛可以在 \(O(n^{3/4})\) 或预处理 \(O(n^{2/3})\) 的时间复杂度内求出某些积性函数前 \(n\) 项的和。

考虑积性函数 \(f(x)\)，我们要求出 \(s(x)=\sum_{i=1}^{x}f(i)\) 在 \(n\) 的取值 \(s(n)\)。考虑构造另一积性函数 \(g(x)\) 满足 \(g(x)\) 和 \((f*g)(x)\) 都可以快速求出前缀和。那么：

\[ \begin{align*} \sum_{i=1}^{n}(f*g)(i)&=\sum_{i=1}^{n}\sum_{j|i}f(j)g\Bigl(\frac ij\Big)\\ &=\sum_{i=1}^{n}\sum_{j=1}^{\lfloor n/i\rfloor}g(i)f(j)\\ &=\sum_{i=1}^{n}g(i)s\Bigl(\left\lfloor\frac ni\right\rfloor\Bigr) \end{align*} \]

移项：

\[ s(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)s\Bigl(\left\lfloor\frac ni\right\rfloor\Bigr) \]

后面一项用整除分块解决，并且本质不同的 \(s\bigl(\left\lfloor\frac ni\right\rfloor\bigr)\) 只有 \(O(n^{3/4})\) 种，用记忆化即可。

提前筛出 \(s\) 的前 \(n^{2/3}\) 项，可以将时间复杂度降低到 \(O(n^{2/3})\)。

\(f(x)\)	\(g(x)\)	\((f*g)(x)\)
\(\mu(x)\)	\(1(x)\)	\(\epsilon(x)\)
\(\varphi(x)\)	\(1(x)\)	\(\operatorname{id}(x)\)
\(\sigma_k(x)\)	\(\mu(x)\)	\(\operatorname{id}^k(x)\)
\(x\times f(x)\)	\(x\)	\(x\times (f*1)(x)\)
\(x\times f(x)\)	\(x\times g(x)\)	\(x\times (f*g)(x)\)