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。
推一下式子：
\[\begin{aligned} \sum\limits_{i = 1}^n f(i) & = \sum\limits_{ij \le n} g(i) h(j) \\ & = \sum\limits_{i = 1}^n h(i) \sum\limits_{j = 1}^{\left\lfloor\frac{n}{i}\right\rfloor} g(j) \end{aligned} \]因此我们只用枚举所有 \(\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\) 有：
\[f(p^k) = \sum\limits_{i = 0}^k g(p^i) h(p^{k - i}) \]因此：
\[h(p^k) = f(p^k) - \sum\limits_{i = 0}^{k - 1} g(p^{k - i}) h(p^i) \]进而可以暴力在 \(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}})\)，瓶颈在杜教筛。
标签：le,limits,sum,Powerful,Number,sqrt,PN,复杂度 From： https://www.cnblogs.com/zltzlt-blog/p/17744949.html