最终得对抗自己

杜教筛公式简易推导

记个笔记, 公式存储空间只有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的卷积就可以搞定啦!

   

加入讨论

电子邮件地址不会被公开。 必填项已用*标注

关于本站

这是Hineven的博客!
主要保存蒟蒻的解题报告(笔记)
还有发布分享一些奇怪的东西

你可以通过上面的↑友情链接
访问Socialists的其他博客。

The Socialists!

我们的Site:socialists.studio
访问量:

AmazingCounters.com