一种 $O\left(n^{\frac 23}\right)$ 计算积性函数前缀和的算法。

设 $f$、$g$ 为积性函数，$S(n)=\sum_{i=1}^n f(i)$，考虑 $f$、$g$ 的狄利克雷卷积的前缀和

\begin{equation}\sum_{i=1}^n (f\ast g)(i)=\sum_{i=1}^n\sum_{d\mid i}f(\frac id)g(d)=\sum_{d=1}^n \left(g(d)\sum_{k=1}^{\lfloor\frac nd\rfloor}f(k)\right)=\sum_{d=1}^n g(d)S(\lfloor\frac nd\rfloor)\end{equation}

所以有

\begin{equation}\sum_{i=1}^n (f\ast g)(i)=g(1)S(n)+\sum_{d=2}^n g(d)S(\lfloor\frac nd\rfloor)\end{equation}

变形得

\begin{equation}g(1)S(n)=\sum_{i=1}^n (f\ast g)(i)-\sum_{d=2}^n g(d)S(\lfloor\frac nd\rfloor)\tag{1}\end{equation}

观察式子，发现如果能快速求出 $(f\ast g)(n)$ 和 $g(n)$ 的前缀和，就可以通过整数分块和记忆化搜索快速求出 $S(n)$。

下面假设 $(f\ast g)(n)$ 和 $g(n)$ 的前缀和可以 $O(1)$ 求出。

若要求出 $S(n)$，需要先求出 $S(\lfloor\frac nd\rfloor)(d=1\sim n)$。