接卷积
杜教筛
为了改模拟考试题被迫学的
参考这篇blog
设有积性函数 \(f(x)\), 求 $ \sum\limits_{i = 1}^ n {f(x)} $。
当数据范围太大(如[1, 1e9])时无法直接计算，要考虑使用复杂度小于先线性的做法。
我们想到数论分块，但大多数时候无法直接使用，考虑找个函数 \(g(n)\) 与 \(f(n)\) 卷起来，得到更好维护的式子。
我们设 \(S(n)=\sum\limits_{i=1}^{n}f(i)\)
设 \(g(n)\) 和 \(f(n)\) 卷起来后的前缀和：
\[\begin{aligned} &= \sum\limits_{i = 1}^{n} \sum\limits_{d | i} f(d) g(\frac{i}{d}) \\ &= \sum\limits_{d = 1}^{n}{g(d)} \sum\limits_{i = 1}^{\lfloor \frac{n}{d}\rfloor } f(i) \\ &= \sum\limits_{d = 1}^{n} g(d) S(\left\lfloor \frac{n}{d} \right\rfloor) \end{aligned} \]考虑 \(g(1)S(n)\) 发现:
\[\begin{aligned} g(1)S(n) &= \sum\limits_{i = 1}^{n}{g(i)S(\left\lfloor\frac{n}{i}\right\rfloor)} - \sum\limits_{i = 2}^{n}{g(i)S(\left\lfloor\frac{n}{i}\right\rfloor)} \\ &= \sum\limits_{i = 1}^{n}{(f * g)(i)} - \sum\limits_{i = 2}^{n}{g(i)S(\left\lfloor\frac{n}{i}\right\rfloor)} \end{aligned} \]则得到杜教筛的模板式：
\[\begin{aligned} g(1)S(n) &= \sum\limits_{i = 1}^{n}{(f * g)(i)} - \sum\limits_{i = 2}^{n}{g(i)S(\left\lfloor\frac{n}{i}\right\rfloor)} \end{aligned} \]之后的工作就是找到那个合适的 \(g\) 函数
要求可以在复杂度 \(O(1)\) 或 \(O(\sqrt{n})\)的情况下求出 \(\sum\limits_{i=1}^{n}(f*g)(i)\) ，否则无法递归求出解
找到\(g\)后剩下的就是数论分块加递归求解加记忆化了
标签：lfloor,frac,limits,sum,rfloor,杜教,aligned From： https://www.cnblogs.com/Eakang/p/16908082.html