Powerful Number 筛

题目:

image.png

Powerful Number 筛也是一种筛,它是 $O(\sqrt n)$ 的。应用时必须满足

  • 它是积性函数

  • 这个东西在质数处取值的函数可以快速计算前缀和。例如此题,显然有 $f(p) = 1$ 。

首先 Powerful Number 的定义,是所有质因子次数都 $\ge 2$ 的数。这种数的个数是 $O(\sqrt n)$ 级别的。因为显然,每个这样的数都可以被表示成 $a^2b^3$ ,所以寻找这种数的时候可以暴力枚举这里的 $a,b$ ,复杂度是 $\sum_{i=1}^{\sqrt n} (\frac n {i^2})^{\frac 1 3}$ ,这个东西积分一下会发现是 $O(\sqrt n)$ 的。

现在,假设我们已经有了一个函数 $f’(p) = f(p),p \in \text{prime}$ 。现在我们想通过这个东西容斥出 $f$ 。具体来说,我们来尝试找到一个容斥系数 $h$ ,满足

显然我们有

因此我们有 $h(p) = 0$ 。所以 $h$ 仅在 Powerful Number 处有值!

因此有

后面那个东西的前缀和事可以求的,而前面这个东西仅在 Powerful Number 处取值。

文章作者: yijan
文章链接: https://yijan.co/2021/02/18/powerful-number-shai/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog