杜教筛
公式
\[ g(1)\sum_{i=1}^nf(i)=\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i) \]
使用
很多时候我们会碰到求积性函数前缀和的情况,由于积性函数的前缀和不一定依然是积性函数,所以我们需要使用一些技巧。
比如给你一个积性函数\(f(x)\), 现在要求你计算\(\begin{aligned}\sum_{i=1}^n f(x)\end{aligned}\)。
如果有机会,我们需要根据自己的经验,选择一个合适的积性函数\(g(x)\),然后与积性函数\(f(x)\)进行狄利克雷卷积运算。即\(\begin{aligned}(f*g)(n)=\sum_{d|n}f(d)\cdot g(\frac{n}{d})\end{aligned}\)
对其计算前缀和 \[ \begin{aligned} &\sum_{i=1}^n(f*g)(i) \\&=\sum_{i=1}^n\sum_{d|i}f(\frac{i}{d})\cdot g(d) \\&=\sum_{d=1}^n\sum_{d|i}f(\frac{i}{d})\cdot g(d) \\&=\sum_{d=1}^n g(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i) \\&=g(1)\sum_{i=1}^n f(x)+\sum_{d=2}^n g(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i) \end{aligned} \]
稍作变形 \[ g(1)\sum_{i=1}^nf(i)=\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i) \]
我们发现右边等式的第一项为前缀和,这里要求我们可以快速计算\(f*g\)的前缀和
对于第二项,我们可以使用分块的整除方案,这里要求\(g\)的前缀和可以快速计算。
1 | /* |