最终得对抗自己

杜教筛公式简易推导

记个笔记, 公式存储空间只有1kb的我就不用记这玩意啦!

首先用狄雷克利卷积:

$$ (f\cdot g)(i) = \sum_{d|i} f(d)g(\frac{i}{d}) $$

求前缀和:

$$ \sum_{i=1}^n (f\cdot g)(i) = \sum_{i=1}^n \sum_{d|i} f(d)g(\frac{i}{d}) $$

把右边求和后面的因子d提前, 设S函数为f的前缀和, 那么有

$$ \sum_{i=1}^n (f\cdot g)(i) = \sum_{d=1}^n g(d) S(\lfloor \frac{n}{d} \rfloor) $$

然后把右边d=1的情况提出来, 把d>1的求和移动到左边:

$$ \sum_{i=1}^n (f\cdot g)(i) -\sum_{d=2}^n g(d) S(\lfloor \frac{n}{d} \rfloor)=g(1)S(n)$$

如果要求S(n), 只要能快速求g(1), g和f的卷积就可以搞定啦!

Join the discussion

Your email address will not be published. Required fields are marked *