洲阁筛
前置知识
定义
洲阁筛是一种能在亚线性时间复杂度内求出大多数积性函数前缀和的筛法．
下面将以求解 𝑛∑𝑖=1𝑓(𝑖)∑i=1nf(i)
为例，具体阐述洲阁筛的原理．
约定
- ℙP 表示质数集，𝑝𝑖pi 表示第 𝑖i 个质数．
- 𝑚m 表示 √𝑛n 内的质数个数．
要求
当 𝑝 ∈ℙ,𝑐 ∈ℕp∈P,c∈N 时，𝑓(𝑝𝑐)f(pc) 为一个关于 𝑝p 的低阶多项式．
思想
- 对于任意 [1,𝑛][1,n] 内的整数，其至多只有一个 >√𝑛>n 的质因子．
- 利用 ⌊𝑛𝑖⌋(𝑖 ∈[1,𝑛] ∩ℕ)⌊ni⌋(i∈[1,n]∩N) 只有 √𝑛n 级别个取值的性质来降低时间复杂度．
过程
将 [1,𝑛][1,n] 内的所有整数按是否有 >√𝑛>n 的质因子分为两类：
𝑛∑𝑖=1𝑓(𝑖)=𝑛∑𝑖=1[∃𝑑∈(√𝑛,𝑛]∩ℙ,𝑑∣𝑖]𝑓(𝑖)+𝑛∑𝑖=1[∀𝑑∈(√𝑛,𝑛]∩ℙ,𝑑∤𝑖]𝑓(𝑖)∑i=1nf(i)=∑i=1n[∃d∈(n,n]∩P,d∣i]f(i)+∑i=1n[∀d∈(n,n]∩P,d∤i]f(i)
对于前半部分，枚举最大因子，根据积性函数的性质可以转换：
𝑛∑𝑖=1𝑓(𝑖)=√𝑛∑𝑖=1𝑓(𝑖)⋅⎛⎜ ⎜ ⎜⎝⌊𝑛𝑖⌋∑𝑑=⌊√𝑛⌋+1[𝑑∈ℙ]𝑓(𝑑)⎞⎟ ⎟ ⎟⎠+𝑛∑𝑖=1[∀𝑑∈(√𝑛,𝑛]∩ℙ,𝑑∤𝑖]𝑓(𝑖)∑i=1nf(i)=∑i=1nf(i)⋅(∑d=⌊n⌋+1⌊ni⌋[d∈P]f(d))+∑i=1n[∀d∈(n,n]∩P,d∤i]f(i)
前后部分可以分别计算．
Part 1
计算 √𝑛∑𝑖=1𝑓(𝑖) ⋅⎛⎜ ⎜ ⎜⎝⌊𝑛𝑖⌋∑𝑑=⌊√𝑛⌋+1[𝑑∈ℙ]𝑓(𝑑)⎞⎟ ⎟ ⎟⎠∑i=1nf(i)⋅(∑d=⌊n⌋+1⌊ni⌋[d∈P]f(d))
考虑枚举 𝑖i，然后 𝑂(1)O(1) 计算括号内部分．
记 𝑔(𝑡,𝑙) =𝑙∑𝑖=1[∀𝑗 ∈[1,𝑡],gcd(𝑖,𝑝𝑗) =1]𝑓(𝑖)g(t,l)=∑i=1l[∀j∈[1,t],gcd(i,pj)=1]f(i)，即 [1,𝑙][1,l] 中与 𝑝1,𝑝2,…,𝑝𝑡p1,p2,…,pt 均互质的数的 𝑓f 值之和．
这样 Part 1 的计算就变成了 √𝑛∑𝑖=1𝑓(𝑖) ⋅𝑔(𝑚,⌊𝑛𝑖⌋)∑i=1nf(i)⋅g(m,⌊ni⌋)．
边界 𝑔(0,𝑙) =∑𝑙𝑖=1𝑓(𝑖)g(0,l)=∑i=1lf(i)，转移 𝑔(𝑡,𝑙) =𝑔(𝑡 −1,𝑙) −𝑓(𝑝𝑡) ⋅𝑔(𝑡−1,⌊𝑙𝑝𝑡⌋)g(t,l)=g(t−1,l)−f(pt)⋅g(t−1,⌊lpt⌋)．
𝑙l 共有 √𝑛n 级别种取值，对于每种取值则需要枚举其质因子，所以复杂度为 𝑂(√𝑛ln√𝑛⋅√𝑛) =𝑂(𝑛log𝑛)O(nlnn⋅n)=O(nlogn)，需要优化．
注意到 𝑝2𝑡+1 >𝑙pt+12>l 时符合条件的数只有 11，所以此时 𝑔(𝑡,𝑙) =𝑓(1) =1g(t,l)=f(1)=1．
代入递推式可得：当 𝑝2𝑡 >𝑙pt2>l 时，𝑔(𝑡,𝑙) =𝑔(𝑡 −1,𝑙) −𝑓(𝑝𝑡)g(t,l)=g(t−1,l)−f(pt)．
所以一旦发现 𝑝2𝑡 >𝑙pt2>l 就停止转移，记此时的 𝑡t 为 𝑡𝑙tl，则 ∀𝑡 >𝑡𝑙,𝑔(𝑡,𝑙) =𝑔(𝑡𝑙,𝑙) −∑𝑡−1𝑖=𝑡𝑙𝑓(𝑝𝑖)∀t>tl,g(t,l)=g(tl,l)−∑i=tlt−1f(pi)．
预处理质数的 𝑓f 值前缀和即可快速求出 𝑔g，时间复杂度被优化至 𝑂(𝑛34log𝑛)O(n34logn)．
Part 2
计算 𝑛∑𝑖=1[∀𝑑∈(√𝑛,𝑛]∩ℙ,𝑑∤𝑖]𝑓(𝑖)∑i=1n[∀d∈(n,n]∩P,d∤i]f(i)
记 ℎ(𝑡,𝑙) =𝑙∑𝑖=1[𝑖=𝑚∏𝑗=𝑡𝑝𝑐𝑗𝑗,𝑐𝑗∈ℕ]𝑓(𝑖)h(t,l)=∑i=1l[i=∏j=tmpjcj,cj∈N]f(i)，即 [1,𝑙][1,l] 中所有只含 𝑝𝑡,𝑝𝑡+1,…,𝑝𝑚pt,pt+1,…,pm 质因子的数的 𝑓f 值之和．
Part 2 即为求 ℎ(0,𝑛)h(0,n)．
边界 ℎ(𝑚 +1,𝑙) =1h(m+1,l)=1，转移 ℎ(𝑡,𝑙) =ℎ(𝑡 +1,𝑙) +∑𝑐∈ℕ∗𝑓(𝑝𝑐𝑡) ⋅ℎ(𝑡+1,⌊𝑙𝑝𝑐𝑡⌋)h(t,l)=h(t+1,l)+∑c∈N∗f(ptc)⋅h(t+1,⌊lptc⌋)．
𝑙l 共有 √𝑛n 级别种取值，所以直接转移复杂度为 𝑂(√𝑛⋅√𝑛ln√𝑛) =𝑂(𝑛log𝑛)O(n⋅nlnn)=O(nlogn)，需要优化．
与 𝑔g 的优化方式类似，注意到 𝑝𝑡 >𝑙pt>l 时，能用 𝑝𝑡,𝑝𝑡+1,…,𝑝𝑚pt,pt+1,…,pm 组成的数只有 11，此时的 ℎ(𝑡,𝑙) =𝑓(1) =1h(t,l)=f(1)=1．
类似的，推出 ∀𝑝2𝑡 >𝑙,ℎ(𝑡,𝑙) =ℎ(𝑡 +1,𝑙) +𝑓(𝑝𝑡)∀pt2>l,h(t,l)=h(t+1,l)+f(pt)．
所以一旦发现 𝑝2𝑡 >𝑙pt2>l 就停止转移，记此时的 𝑡t 为 𝑡𝑙tl，之后用到 ℎh 时，把此时的 ℎh 值加上 min(𝑙,√𝑛)∑𝑖=𝑝𝑡𝑙[𝑖 ∈ℙ]𝑓(𝑖)∑i=ptlmin(l,n)[i∈P]f(i) 即可．
时间复杂度被优化至 𝑂(𝑛34log𝑛)O(n34logn)．
求和
算出了 Part 1 和 Part 2 的答案，将其相加即为 𝑛∑𝑖=1𝑓(𝑖)∑i=1nf(i)．
参考
积性函数线性筛/杜教筛/洲阁筛学习笔记 | Bill Yang's Blog
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Early0v0, Enter-tainer, Tiphereth-A, Xeonacid, AlephInfinity1, billchenchina, CCXXXI, Great-designer, iamtwz, Nanarikom, ouuan, scp020, shuzhouliu, StudyingFather 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用