Powerful Number 筛

题目:

image.png

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

  • 它是积性函数

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

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

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

f(x)=dxf(d)h(dx)h=f/ff(x) = \sum_{d|x} f'(d)h(\frac d x)\\ h = f / f'

显然我们有

h(1)=1h(1)f(p)+h(p)f(1)=f(p)f(p)+h(p)f(1)=f(p)h(1) = 1\\ h(1)f'(p) + h(p)f'(1) = f(p)\\ f'(p) + h(p)f'(1) = f(p)

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

因此有

i=1nf(i)=i=1npq=ih(p)f(q)=pqnh(p)f(q)=ph(p)qn/pf(q)\begin{aligned} &\sum_{i=1}^n f(i)\\ =&\sum_{i=1}^n \sum_{pq = i} h(p)f'(q)\\ =& \sum_{pq \le n} h(p)f'(q)\\ =& \sum_{p} h(p) \sum_{q \le n/p} f'(q) \end{aligned}

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

\