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

- 阅读全文 -