对于一类函数求和，诸如
$$
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$满足狄利克雷卷积关系
