前情提要：$O(n^{0.75}/\log n)$ 时间的积性函数求和。当 $n \ge 10^{12}$ 的时候需要十几秒出解。

如果积性函数的性质更好，那么我们可以更快地求和。

假设积性函数 $f$ 和易于求和的积性函数 $g$ 满足 $f(p)=g(p)$，且 $f=g*h$, $g*h$ 表示 $g, h$ 的狄利克雷卷积，也就是 $f(n)=\sum_{d|n}g(d)h\left({n \over d}\right)$.

那么我们函数 $h$ 可能比较难看，但是它具有性质：$h(p)=0$. 这意味着，凡是满足 $h(n) \ne 0$ 的数都是powerful number, 换句话说它的每个素因子次数都不小于 $2$.

Powerful number 可以写成 $a^2b^3$ 的形式。

$\sum_{b=1}^{\sqrt[3]n}\sqrt{n \over b^3}=O\left(\sqrt n\int_{1}^{\sqrt[3]n}t^{-1.5}\mathrm dt\right)=O(\sqrt n)$

所以 powerful number 的个数是 $O(\sqrt n)$.

设 $G$ 是 $g$ 的前缀和。现在我们有：

$$\sum_{i=1}^nf(i)=\sum_{i=1}^n\sum_{j|i}g\left({i \over j}\right)h(j)=\sum_{[j \le n, j\text{ is powerful}]}^nh(j)G\left({n \over j}\right)$$

于是如果我们已经对于所有 powerful number $i$ 求出 $g\left({n \over i}\right)$, 则后续的积性函数求和步骤将在 $O(\sqrt n)$ 时间内完成。

当然 $g$ 的求和可能会比较难做。一些特殊的数论函数可能可以杜教筛求和。比较有意思的是这么一个例子：

题目来源：钟子谦。这是他的 powerful number 求和法博客链接。

设积性函数 $f$ 满足 $f(p^c)=2^c$, 求 $\sum_{i=1}^N f(i)$, $N \le 10^{12}$.

注意到 $f(p)=2$, 设 $g(n)$ 表示 $n$ 的约数个数，$g(p)=2=f(p)$. 再构造 $h(p^c)=2^{c-2}(c \ge 2)$, 得 $f=g*h$.

由于 $G(n)=\sum_{i=1}^n\sum_{j|i}1=\sum_{ij \le n}1=2\sum_{i=1}^{\lfloor\sqrt n\rfloor}\left\lfloor{n \over i}\right\rfloor-(\lfloor\sqrt n\rfloor)^2$, 可在 $O(\sqrt n)$ 时间内求 $G(n)$.

所以对于所有 $k={n \over a^2b^3}$ 求 $G(k)$, 时间复杂度为 $O\left(\sum_{a, b}\sqrt{n \over a^2b^3}\right)=O\left(\sum_{a}\sqrt{n \over a^2}\right)=O(\sqrt n\log n)$.