杜教筛

我们要求的是\(F(n)=\sum_{i=1}^{n}f(i)\)，现在有\(h=f*g\)，\(G(x),H(x)\)分别为\(g(x),h(x)\)的前缀和。

\[ \begin{aligned} H(n)=&\sum_{i=1}^{n}h(i)\\ =&\sum_{i=1}^{n}\sum_{d|i}f(\frac{i}{d})g(d)\\ =&\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}f(i)\\ =&\sum_{d=1}^{n}g(d)F(\lfloor \frac{n}{d} \rfloor)\\ g(1)F(n)=H(n)-&\sum_{d=2}^{n}g(d)F(\lfloor \frac{n}{d} \rfloor) \end{aligned} \]

（updating...）