Powerful Number 筛(PN 筛)可以解决一些求积性函数前缀和的问题。要求能构造出一个积性函数 \(g\),满足:
- \(g\) 容易求前缀和;
- 对于质数 \(p\),\(f(p) = g(p)\)。
称一个数 \(x\) 是 Powerful Number(PN)当且仅当 \(x\) 的质因数分解中,所有质因数的指数都 \(\ge 2\)。\(1\) 是 PN。
有结论 \(\le n\) 的 PN 有 \(O(\sqrt{n})\) 个。并且若线性筛出 \(\le \sqrt{n}\) 的所有质数,枚举每个质数的指数,就可以在 \(O(\sqrt{n})\) 的时间复杂度内搜索出所有 PN。
假设我们已经构造出一个满足条件的 \(g\)。假设有一个积性函数 \(h\),满足 \(f = g * h\)。那么有 \(f(p) = g(1) h(p) + g(p) h(1) = g(p) + h(p)\),又因为 \(f(p) = g(p)\),所以 \(h(p) = 0\)。所以 \(h(x)\) 有值当且仅当 \(x\) 是 PN。
推一下式子:
因此我们只用枚举所有 \(\le n\) 的 PN,然后快速计算 \(\sum\limits_{j = 1}^{\left\lfloor\frac{n}{i}\right\rfloor} g(j)\) 即可。
问题来到如何计算 \(h(i)\)。因为 \(h\) 是积性函数,所以只用考虑如何计算 \(h(p^k)\)。根据 \(f = g * h\) 有:
因此:
进而可以暴力在 \(O(\sqrt{n})\) 的时间复杂度内计算。
若 \(g\) 的前缀和能快速计算,那么 PN 筛的时间复杂度为 \(O(\sqrt{n})\)。
例题
1. P5325 【模板】Min_25 筛
考虑构造 \(g = (id \cdot \varphi)\),那么 \(g\) 的前缀和可以使用杜教筛计算(\(id^2 = (id \cdot \varphi) * id\))。
时间复杂度 \(O(n^{\frac{2}{3}})\),瓶颈在杜教筛。