题目:
Powerful Number 筛也是一种筛,它是 O(n) 的。应用时必须满足
首先 Powerful Number 的定义,是所有质因子次数都 ≥2 的数。这种数的个数是 O(n) 级别的。因为显然,每个这样的数都可以被表示成 a2b3 ,所以寻找这种数的时候可以暴力枚举这里的 a,b ,复杂度是 ∑i=1n(i2n)31 ,这个东西积分一下会发现是 O(n) 的。
现在,假设我们已经有了一个函数 f′(p)=f(p),p∈prime 。现在我们想通过这个东西容斥出 f 。具体来说,我们来尝试找到一个容斥系数 h ,满足
f(x)=d∣x∑f′(d)h(xd)h=f/f′
显然我们有
h(1)=1h(1)f′(p)+h(p)f′(1)=f(p)f′(p)+h(p)f′(1)=f(p)
因此我们有 h(p)=0 。所以 h 仅在 Powerful Number 处有值!
因此有
===i=1∑nf(i)i=1∑npq=i∑h(p)f′(q)pq≤n∑h(p)f′(q)p∑h(p)q≤n/p∑f′(q)
后面那个东西的前缀和事可以求的,而前面这个东西仅在 Powerful Number 处取值。
\