本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-09 11:37:09

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

假设存在一个积性函数 $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)$
$=\sum\limits_{d=1}^n f(d)S(\lfloor \frac{n}{d}\rfloor)$。

由此可得，$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 定理可以证明复杂度，不写了。