积性函数前缀和科技 - 杜教筛

· · 个人记录

我不知道发明者是怎么想到这些的。

假设存在一个积性函数 f，给定一个 n，要求 \sum\limits_{i=1}^nf(i)。

设 S(n) = \sum\limits_{i=1}^nf(i)。

考虑另一个积性函数 g，它们的 Dirchlet 卷积的前缀和：

\sum\limits_{i=1}^n (f*g)(i) = \sum\limits_{i=1}^n \sum\limits_{d|i}f(d)g(\frac{i}{d}) =\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}f(\frac{di}{d}) =\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}f(i) 由此可得，$f(1)S(n) =\sum\limits_{i=1}^n(f*g)(i)- \sum\limits_{d=2}^nf(d)S(\lfloor\frac{n}{d}\rfloor)$。 现在的主要任务在于找到一个函数 $g$，使得 $f*g$ 的前缀和可以快速求出。另外，$\sum\limits_{d=2}^nf(d)S(\lfloor\frac{n}{d}\rfloor)$ 可以使用整除分块计算。 假设 $f*g$ 的前缀和可以 $O(1)$ 计算，那么最后整个算法的复杂度是 $O(n^{\frac{2}{3}})$ 的，前提是使用线性筛预处理出 $f$ 的前 $n^{\frac{2}{3}}$ 的值的前缀和。 Master 定理可以证明复杂度，不写了。