狄利克雷卷积前缀和

给定积性函数 $f,g$，且已经得到 $f,g$ 所有 $\lfloor\frac{n}{i}\rfloor$ 处的前缀和 $F,G$，现在要求 $h=f*g$ 所有 $\lfloor\frac{n}{i}\rfloor$ 处的前缀和。

简单推导后可得：

$$
H(n)=\sum\limits_{i=1}^nf(i)G(\frac{n}{i})
$$

可以整数分块，对于所有的 $\lfloor\frac{n}{i}\rfloor$ 来说，如果直接做的话，复杂度是：

$$
\int _1^{\sqrt{n}}\sqrt{\frac{n}{x}}dx=n^{\frac{3}{4}}
$$

实际上，我们可以利用杜教筛一样的预处理，对于所有 $n^{\frac{2}{3}}$ 以内的 $\lfloor\frac{n}{i}\rfloor$，全都预处理。这样的复杂度应该为：

$$
\int _1^{n^{\frac{1}{3}}}\sqrt{\frac{n}{x}}dx=O(n^{\frac{2}{3}})
$$

由于 $h$ 是积性函数，所以可以利用线性筛直接筛出来，预处理的部分复杂度也是 $O(n^{\frac{2}{3}})$ 的。