Powerful Number 筛
定义
Powerful Number（以下简称 PN）筛类似于杜教筛，或者说是杜教筛的一个扩展，可以拿来求一些积性函数的前缀和．
要求 ：
- 存在一个函数 𝑔g
满足： - 𝑔g 是积性函数．
- 𝑔g 易求前缀和．
- 对于质数 𝑝p，𝑔(𝑝) =𝑓(𝑝)g(p)=f(p)．
假设现在要求积性函数 𝑓f 的前缀和 𝐹(𝑛) =∑𝑛𝑖=1𝑓(𝑖)F(n)=∑i=1nf(i)．
Powerful Number
定义 ：对于正整数 𝑛n，记 𝑛n 的质因数分解为 𝑛 =∏𝑚𝑖=1𝑝𝑒𝑖𝑖n=∏i=1mpiei．𝑛n 是 PN 当且仅当 ∀1 ≤𝑖 ≤𝑚,𝑒𝑖 >1∀1≤i≤m,ei>1．
性质 1 ：所有 PN 都可以表示成 𝑎2𝑏3a2b3 的形式．
证明 ：若 𝑒𝑖ei 是偶数，则将 𝑝𝑒𝑖𝑖piei 合并进 𝑎2a2 里；若 𝑒𝑖ei 为奇数，则先将 𝑝3𝑖pi3 合并进 𝑏3b3 里，再将 𝑝𝑒𝑖−3𝑖piei−3 合并进 𝑎2a2 里．
性质 2 ：𝑛n 以内的 PN 至多有 𝑂(√𝑛)O(n) 个．
证明 ：考虑枚举 𝑎a，再考虑满足条件的 𝑏b 的个数，有 PN 的个数约等于
∫√𝑛13√𝑛𝑥2d𝑥=𝑂(√𝑛)∫1nnx23dx=O(n)
那么如何求出 𝑛n 以内所有的 PN 呢？线性筛找出 √𝑛n 内的所有素数，再 DFS 搜索各素数的指数即可．由于 𝑛n 以内的 PN 至多有 𝑂(√𝑛)O(n) 个，所以至多搜索 𝑂(√𝑛)O(n) 次．
PN 筛
首先，构造出一个易求前缀和的积性函数 𝑔g，且满足对于素数 𝑝p，𝑔(𝑝) =𝑓(𝑝)g(p)=f(p)．记 𝐺(𝑛) =∑𝑛𝑖=1𝑔(𝑖)G(n)=∑i=1ng(i)．
然后，构造函数 ℎ =𝑓/𝑔h=f/g，这里的 // 表示狄利克雷卷积除法．根据狄利克雷卷积的性质可以得知 ℎh 也为积性函数，因此 ℎ(1) =1h(1)=1．𝑓 =𝑔 ∗ℎf=g∗h，这里 ∗∗ 表示狄利克雷卷积．
对于素数 𝑝p，𝑓(𝑝) =𝑔(1)ℎ(𝑝) +𝑔(𝑝)ℎ(1) =ℎ(𝑝) +𝑔(𝑝) ⟹ ℎ(𝑝) =0f(p)=g(1)h(p)+g(p)h(1)=h(p)+g(p)⟹h(p)=0．根据 ℎ(𝑝) =0h(p)=0 和 ℎh 是积性函数可以推出对于非 PN 的数 𝑛n 有 ℎ(𝑛) =0h(n)=0，即 ℎh 仅在 PN 处取有效值．
现在，根据 𝑓 =𝑔 ∗ℎf=g∗h 有
𝐹(𝑛)=𝑛∑𝑖=1𝑓(𝑖)=𝑛∑𝑖=1∑𝑑|𝑖ℎ(𝑑)𝑔(𝑖𝑑)=𝑛∑𝑑=1⌊𝑛𝑑⌋∑𝑖=1ℎ(𝑑)𝑔(𝑖)=𝑛∑𝑑=1ℎ(𝑑)⌊𝑛𝑑⌋∑𝑖=1𝑔(𝑖)=𝑛∑𝑑=1ℎ(𝑑)𝐺(⌊𝑛𝑑⌋)=𝑛∑𝑑=1𝑑 is PNℎ(𝑑)𝐺(⌊𝑛𝑑⌋)F(n)=∑i=1nf(i)=∑i=1n∑d|ih(d)g(id)=∑d=1n∑i=1⌊nd⌋h(d)g(i)=∑d=1nh(d)∑i=1⌊nd⌋g(i)=∑d=1nh(d)G(⌊nd⌋)=∑d=1d is PNnh(d)G(⌊nd⌋)
𝑂(√𝑛)O(n) 找出所有 PN，计算出所有 ℎh 的有效值．对于 ℎh 有效值的计算，只需要计算出所有 ℎ(𝑝𝑐)h(pc) 处的值，就可以根据 ℎh 为积性函数推出 ℎh 的所有有效值．现在对于每一个有效值 𝑑d，计算 ℎ(𝑑)𝐺(⌊𝑛𝑑⌋)h(d)G(⌊nd⌋) 并累加即可得到 𝐹(𝑛)F(n)．
下面考虑计算 ℎ(𝑝𝑐)h(pc)，一共有两种方法：一种是直接推出 ℎ(𝑝𝑐)h(pc) 仅与 𝑝,𝑐p,c 有关的计算公式，再根据公式计算 ℎ(𝑝𝑐)h(pc)；另一种是根据 𝑓 =𝑔 ∗ℎf=g∗h 有 𝑓(𝑝𝑐) =∑𝑐𝑖=0𝑔(𝑝𝑖)ℎ(𝑝𝑐−𝑖)f(pc)=∑i=0cg(pi)h(pc−i)，移项可得 ℎ(𝑝𝑐) =𝑓(𝑝𝑐) −∑𝑐𝑖=1𝑔(𝑝𝑖)ℎ(𝑝𝑐−𝑖)h(pc)=f(pc)−∑i=1cg(pi)h(pc−i)，现在就可以枚举素数 𝑝p 再枚举指数 𝑐c 求解出所有 ℎ(𝑝𝑐)h(pc)．
过程
- 构造 𝑔g
- 构造快速计算 𝐺G 的方法
- 计算 ℎ(𝑝𝑐)h(pc)
- 搜索 PN，过程中累加答案
- 得到结果
对于第 3 步，可以直接根据公式计算，可以使用枚举法预处理打表，也可以搜索到了再临时推．
性质
以使用第二种方法计算 ℎ(𝑝𝑐)h(pc) 为例进行分析．可以分为计算 ℎ(𝑝𝑐)h(pc) 和搜索两部分进行分析．
对于第一部分，根据 𝑂(√𝑛)O(n) 内的素数个数为 𝑂(√𝑛log𝑛)O(nlogn)，每个素数 𝑝p 的指数 𝑐c 至多为 log𝑛logn，计算 ℎ(𝑝𝑐)h(pc) 需要循环 (𝑐 −1)(c−1) 次，由此有第一部分的时间复杂度为 𝑂(√𝑛log𝑛⋅log𝑛⋅log𝑛) =𝑂(√𝑛log𝑛)O(nlogn⋅logn⋅logn)=O(nlogn)，且这是一个宽松的上界．根据题目的不同还可以添加不同的优化，从而降低第一部分的时间复杂度．
对于搜索部分，由于 𝑛n 以内的 PN 至多有 𝑂(√𝑛)O(n) 个，所以至多搜索 𝑂(√𝑛)O(n) 次．对于每一个 PN，根据计算 𝐺G 的方法不同，时间复杂度也不同．例如，假设计算 𝐺(⌊𝑛𝑑⌋)G(⌊nd⌋) 的时间复杂度为 𝑂(1)O(1)，则第二部分的复杂度为 𝑂(√𝑛)O(n)．
特别地，若借助杜教筛计算 𝐺(⌊𝑛𝑑⌋)G(⌊nd⌋)，则第二部分的时间复杂度为杜教筛的时间复杂度，即 𝑂(𝑛23)O(n23)．因为若事先计算一次 𝐺(𝑛)G(n)，并且预先使用线性筛优化和用支持快速随机访问的数据结构（如 C++ 中的 std::map 和 std::unordered_map）记录较大的值，则杜教筛过程中用到的 𝐺(⌊𝑛𝑑⌋)G(⌊nd⌋) 都是线性筛中记录的或者 std::map 中记录的，这一点可以直接用程序验证．
对于空间复杂度，其瓶颈在于存储 ℎ(𝑝𝑐)h(pc)．若使用二维数组 𝑎a 记录，𝑎𝑖,𝑗ai,j 表示 ℎ(𝑝𝑗𝑖)h(pij) 的值，则空间复杂度为 𝑂(√𝑛log𝑛⋅log𝑛) =𝑂(√𝑛)O(nlogn⋅logn)=O(n)．
例题
Luogu P5325【模板】Min_25 筛
题意 ：给定积性函数 𝑓(𝑝𝑘) =𝑝𝑘(𝑝𝑘 −1)f(pk)=pk(pk−1)，求 ∑𝑛𝑖=1𝑓(𝑖)∑i=1nf(i)．
易得 𝑓(𝑝) =𝑝(𝑝 −1) =id(𝑝)𝜑(𝑝)f(p)=p(p−1)=id(p)φ(p)，构造 𝑔(𝑛) =id(𝑛)𝜑(𝑛)g(n)=id(n)φ(n)．
考虑使用杜教筛求 𝐺(𝑛)G(n)，根据 (id ⋅𝜑) ∗id =id2(id⋅φ)∗id=id2 可得 𝐺(𝑛) =∑𝑛𝑖=1𝑖2 −∑𝑛𝑑=2𝑑 ⋅𝐺(⌊𝑛𝑑⌋)G(n)=∑i=1ni2−∑d=2nd⋅G(⌊nd⌋)．
之后 ℎ(𝑝𝑘)h(pk) 的取值可以枚举计算，这种方法不再赘述．
此外，此题还可以直接求出 ℎ(𝑝𝑘)h(pk) 仅与 𝑝,𝑘p,k 有关的公式，过程如下：
𝑓(𝑝𝑘)=𝑘∑𝑖=0𝑔(𝑝𝑘−𝑖)ℎ(𝑝𝑖)⟺𝑝𝑘(𝑝𝑘−1)=𝑘∑𝑖=0𝑝𝑘−𝑖𝜑(𝑝𝑘−𝑖)ℎ(𝑝𝑖)⟺𝑝𝑘(𝑝𝑘−1)=𝑘∑𝑖=0𝑝2𝑘−2𝑖−1(𝑝−1)ℎ(𝑝𝑖)⟺𝑝𝑘(𝑝𝑘−1)=ℎ(𝑝𝑘)+𝑘−1∑𝑖=0𝑝2𝑘−2𝑖−1(𝑝−1)ℎ(𝑝𝑖)⟺ℎ(𝑝𝑘)=𝑝𝑘(𝑝𝑘−1)−𝑘−1∑𝑖=0𝑝2𝑘−2𝑖−1(𝑝−1)ℎ(𝑝𝑖)⟺ℎ(𝑝𝑘)−𝑝2ℎ(𝑝𝑘−1)=𝑝𝑘(𝑝𝑘−1)−𝑝𝑘+1(𝑝𝑘−1−1)−𝑝(𝑝−1)ℎ(𝑝𝑘−1)⟺ℎ(𝑝𝑘)−𝑝ℎ(𝑝𝑘−1)=𝑝𝑘+1−𝑝𝑘⟺ℎ(𝑝𝑘)𝑝𝑘−ℎ(𝑝𝑘−1)𝑝𝑘−1=𝑝−1f(pk)=∑i=0kg(pk−i)h(pi)⟺pk(pk−1)=∑i=0kpk−iφ(pk−i)h(pi)⟺pk(pk−1)=∑i=0kp2k−2i−1(p−1)h(pi)⟺pk(pk−1)=h(pk)+∑i=0k−1p2k−2i−1(p−1)h(pi)⟺h(pk)=pk(pk−1)−∑i=0k−1p2k−2i−1(p−1)h(pi)⟺h(pk)−p2h(pk−1)=pk(pk−1)−pk+1(pk−1−1)−p(p−1)h(pk−1)⟺h(pk)−ph(pk−1)=pk+1−pk⟺h(pk)pk−h(pk−1)pk−1=p−1
再根据 ℎ(𝑝) =0h(p)=0，通过累加法即可推出 ℎ(𝑝𝑘) =(𝑘 −1)(𝑝 −1)𝑝𝑘h(pk)=(k−1)(p−1)pk．
参考代码
---|---
### [「LOJ #6053」简单的函数](https://loj.ac/problem/6053)
给定 𝑓(𝑛)f(n)：
𝑓(𝑛)=⎧{ {⎨{ {⎩1𝑛=1𝑝⊕𝑐𝑛=𝑝𝑐𝑓(𝑎)𝑓(𝑏)𝑛=𝑎𝑏 and 𝑎⟂𝑏f(n)={1n=1p⊕cn=pcf(a)f(b)n=ab and a⟂b
易得：
𝑓(𝑝)={𝑝+1𝑝=2𝑝−1otherwisef(p)={p+1p=2p−1otherwise
构造 𝑔g 为
𝑔(𝑛)={3𝜑(𝑛)2∣𝑛𝜑(𝑛)otherwiseg(n)={3φ(n)2∣nφ(n)otherwise
易证 𝑔(𝑝) =𝑓(𝑝)g(p)=f(p) 且 𝑔g 为积性函数．
下面考虑求 𝐺(𝑛)G(n)．
𝐺(𝑛)=𝑛∑𝑖=1[𝑖mod2=1]𝜑(𝑖)+3𝑛∑𝑖=1[𝑖mod2=0]𝜑(𝑖)=𝑛∑𝑖=1𝜑(𝑖)+2𝑛∑𝑖=1[𝑖mod2=0]𝜑(𝑖)=𝑛∑𝑖=1𝜑(𝑖)+2⌊𝑛2⌋∑𝑖=1𝜑(2𝑖)G(n)=∑i=1n[imod2=1]φ(i)+3∑i=1n[imod2=0]φ(i)=∑i=1nφ(i)+2∑i=1n[imod2=0]φ(i)=∑i=1nφ(i)+2∑i=1⌊n2⌋φ(2i)
记 𝑆1(𝑛) =∑𝑛𝑖=1𝜑(𝑖)S1(n)=∑i=1nφ(i)，𝑆2(𝑛) =∑𝑛𝑖=1𝜑(2𝑖)S2(n)=∑i=1nφ(2i)，则 𝐺(𝑛) =𝑆1(𝑛) +2𝑆2(⌊𝑛2⌋)G(n)=S1(n)+2S2(⌊n2⌋)．
当 2 ∣𝑛2∣n 时，有
𝑆2(𝑛)=𝑛∑𝑖=1𝜑(2𝑖)=𝑛2∑𝑖=1(𝜑(2(2𝑖−1))+𝜑(2(2𝑖)))=𝑛2∑𝑖=1(𝜑(2𝑖−1)+2𝜑(2𝑖))=𝑛2∑𝑖=1(𝜑(2𝑖−1)+𝜑(2𝑖))+𝑛2∑𝑖=1𝜑(2𝑖)=𝑛∑𝑖=1𝜑(𝑖)+𝑆2(𝑛2)=𝑆1(𝑛)+𝑆2(⌊𝑛2⌋)S2(n)=∑i=1nφ(2i)=∑i=1n2(φ(2(2i−1))+φ(2(2i)))=∑i=1n2(φ(2i−1)+2φ(2i))=∑i=1n2(φ(2i−1)+φ(2i))+∑i=1n2φ(2i)=∑i=1nφ(i)+S2(n2)=S1(n)+S2(⌊n2⌋)
当 2 ∤𝑛2∤n 时，有
𝑆2(𝑛)=𝑆2(𝑛−1)+𝜑(2𝑛)=𝑆2(𝑛−1)+𝜑(𝑛)=𝑛−1∑𝑖=1𝜑(𝑖)+𝑆2(𝑛−12)+𝜑(𝑛)=𝑆1(𝑛)+𝑆2(⌊𝑛2⌋)S2(n)=S2(n−1)+φ(2n)=S2(n−1)+φ(n)=∑i=1n−1φ(i)+S2(n−12)+φ(n)=S1(n)+S2(⌊n2⌋)
综上，有 𝑆2(𝑛) =𝑆1(𝑛) +𝑆2(⌊𝑛2⌋)S2(n)=S1(n)+S2(⌊n2⌋)．
𝑆1S1 可以用杜教筛求，𝑆2S2 直接按照公式推，这样 𝐺G 也可以求出来了．
参考代码
---|---
习题
参考资料
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Enter-tainer, Tiphereth-A, Backl1ght, StudyingFather, Xeonacid, cy1999, Great-designer, iamtwz, Ir1d, kenlig, ksyx, LaDeXX, lrherqwq, Marcythm, xyf007 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用