杜教筛
是求一个数论函数f的前缀和，令其为S
我们考虑构造一个数论函数g，根据 狄利克雷卷积
\[\begin{aligned} \sum_{i=1}^{n}(f * g)(i) & =\sum_{i=1}^{n}\sum_{d \mid i}g(d)f\left(\frac{i}{d}\right) \\ & =\sum_{i=1}^{n}g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \end{aligned} \]可以推出
\[\begin{aligned} g(1)S(n) & = \sum_{i=1}^n g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) - \sum_{i=2}^n g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \\ & = \sum_{i=1}^n (f * g)(i) - \sum_{i=2}^n g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \end{aligned} \]所以我们只需快速求出\(g\)和\((f*g)\)的前缀和，就可以快速求出S
然后时间复杂度不会证明，但直接打是\(O(n^{\frac34})\)，预处理前\(O(n^{\frac23})\)位前缀和是\(O(n^{\frac23})\)
预处理+外面套上数论分块也是\(O(n^{\frac23})\)
难点就是构造g函数，所以学习一下数论函数
标签：lfloor,right,frac,sum,笔记,杜教,学习,rfloor,left From： https://www.cnblogs.com/zhy114514/p/18028184