在 \(O(n^{2/3})\) 内求积性函数 \(f\) 的前缀和 \(F(n)=\sum\limits_{i=1}^nf(i)\)。
首先找到一个积性函数 \(g\) 使得 \(g\) 和 \(h(=f*g)\) 的前缀和能够快速求出。
\[\begin{aligned} \sum\limits_{i=1}^nh(i)&=\sum\limits_{i=1}^n\sum\limits_{d\ |\ i}f(\frac{i}{d})g(d) \\&=\sum\limits_{d=1}^n\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}f(i)g(d) \\&=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}f(i) \\&=\sum\limits_{d=1}^ng(d)F(\left\lfloor\frac{n}{d}\right\rfloor) \\&=g(1)F(n)+\sum\limits_{d=2}^ng(d)F(\left\lfloor\frac{n}{d}\right\rfloor) \\&=F(n)+\sum\limits_{d=2}^ng(d)F(\left\lfloor\frac{n}{d}\right\rfloor) \end{aligned}\] \[\Large{F(n)=\sum\limits_{i=1}^nh(i)-\sum\limits_{d=2}^ng(d)F(\left\lfloor\frac{n}{d}\right\rfloor)} \]递归即可。
复杂度证明：