杜教筛

杜教筛其实就是通过一些反演技巧求积性函数的前缀和,能实现 $O(n^\frac{2}{3})$ 的复杂度。本质上还是线性筛加记忆化搜索。这里我们通过介绍欧拉 $\varphi$ 函数的前缀和来讲解杜教筛。如例题 51Nod 1239 - 欧拉函数之和 我们需要求解 $\phi(n)=\sum_{i=1}^{n}{\varphi(i)}$ 而我们需要的反演技巧是 $\sum_{d|n} \varph

- 阅读全文 -

新的开始

我高中时候有个博客,懒得鼓捣也懒得更新,慢慢就放下了(其实还是菜)看到葵酱搭了一个,我也跟风来摸摸鱼(葵酱是真的厉害)最近确实遇到好多小问题,到处搜博客什么的,如果能自己有博客去写一写,就当学习笔记了就这样8因为我文笔确实不好希望我能坚持下去www

- 阅读全文 -