对于一类函数求和,诸如

$$
F(n)=\sum_{i=1}^{n}f(i)
$$

不妨分别从以下两种角度考虑

$f=g \times h$

$$
\begin{align}
F(n)
&=\sum_{i=1}^{n} f(i) \\
&=\sum_{i=1}^{n}\sum_{d \mid i}g(d)h(\frac{i}{d}) \\
&=\sum_{d=1}^{n}g(d)\sum_{i=1 \wedge d \mid i}^{n} h(\frac{i}{d}) \\
&=\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} h(i) \\
&=\sum_{d=1}^{n}g(d)H(\lfloor \frac{n}{d} \rfloor) \\
\end{align}
$$

这不就是数论分块的基本形式嘛

只要$G,H$能快速计算,就可以在$O((T(G)+T(H))\sqrt n)$的时间内计算出答案

$h = f \times g$

$$
\begin{align}
H(n)
&=\sum_{i=1}^{n}h(i) \\
&=\sum_{i=1}^{n}\sum_{d \mid i}f(d)g(\frac{i}{d}) \\
&=\sum_{d=1}^{n}g(d)F(\lfloor \frac{n}{d} \rfloor) \\
&=g(1)F(n)+\sum_{d=2}^{n}g(d)F(\lfloor \frac{n}{d} \rfloor) \\
\Rightarrow
&g(1)F(n)=H(n)-\sum_{d=2}^{n}g(d)F(\lfloor \frac{n}{d} \rfloor)
\end{align}
$$

一般而言预处理$F$的前$n^{\frac{2}{3}}$项的值,对于后$n^{\frac{1}{3}}$项递归计算,时间复杂度为$O(n^{\frac{2}{3}})$


大体来说求$f$的前缀和,就是找两个可以快速计算前缀和的函数$g,h$,使得$f,g,h$满足狄利克雷卷积关系