洲閣篩
前置知識
定義
洲閣篩是一種能在亞線性時間複雜度內求出大多數積性函數前綴和的篩法。
下面將以求解 \(\displaystyle\sum_{i=1}^nf(i)\) 為例，具體闡述洲閣篩的原理。
約定
- \(\mathbb P\) 表示質數集，\(p_i\) 表示第 \(i\) 個質數。
- \(m\) 表示 \(\sqrt n\) 內的質數個數。
要求
當 \(p\in\mathbb P,c\in\mathbb N\) 時，\(f(p^c)\) 為一個關於 \(p\) 的低階多項式。
思想
- 對於任意 \([1,n]\) 內的整數，其至多隻有一個 \(>\sqrt n\) 的質因子。
- 利用 \(\left\lfloor\dfrac ni\right\rfloor(i\in[1,n]\cap\mathbb N)\) 只有 \(\sqrt n\) 級別個取值的性質來降低時間複雜度。
過程
將 \([1,n]\) 內的所有整數按是否有 \(>\sqrt n\) 的質因子分為兩類：
對於前半部分，枚舉最大因子，根據積性函數的性質可以轉換：
前後部分可以分別計算。
Part 1
計算 \(\displaystyle\sum_{i=1}^{\sqrt n}f(i)\cdot\left(\sum_{d=\lfloor\sqrt n\rfloor+1}^{\lfloor\frac ni\rfloor}[d\in\mathbb P]f(d)\right)\)。
考慮枚舉 \(i\)，然後 \(\mathcal O(1)\) 計算括號內部分。
記 \(\displaystyle g(t,l)=\sum_{i=1}^l[\forall j\in[1,t],\gcd(i,p_j)=1]f(i)\)，即 \([1,l]\) 中與 \(p_1,p_2,\dots,p_t\) 均互質的數的 \(f\) 值之和。
這樣 Part 1 的計算就變成了 \(\displaystyle\sum_{i=1}^{\sqrt n}f(i)\cdot g\left(m,\left\lfloor\frac ni\right\rfloor\right)\)。
邊界 \(g(0,l)=\sum_{i=1}^lf(i)\)，轉移 \(g(t,l)=g(t-1,l)-f(p_t)\cdot g\left(t-1,\left\lfloor\frac l{p_t}\right\rfloor\right)\)。
\(l\) 共有 \(\sqrt n\) 級別種取值，對於每種取值則需要枚舉其質因子，所以複雜度為 \(\displaystyle\mathcal O\left(\frac{\sqrt n}{\ln\sqrt n}\cdot\sqrt n\right)=\mathcal O\left(\frac n{\log n}\right)\)，需要優化。
注意到 \(p_{t+1}^2>l\) 時符合條件的數只有 \(1\)，所以此時 \(g(t,l)=f(1)=1\)。
代入遞推式可得：當 \(p_t^2>l\) 時，\(g(t,l)=g(t-1,l)-f(p_t)\)。
所以一旦發現 \(p_t^2>l\) 就停止轉移，記此時的 \(t\) 為 \(t_l\)，則 \(\forall t>t_l,g(t,l)=g(t_l,l)-\sum_{i=t_l}^{t-1}f(p_i)\)。
預處理質數的 \(f\) 值前綴和即可快速求出 \(g\)，時間複雜度被優化至 \(\mathcal O\left(\dfrac{n^{\frac34}}{\log n}\right)\)。
Part 2
計算 \(\displaystyle\sum_{i=1}^n\left[\forall d\in(\sqrt n,n]\cap\mathbb P,d\nmid i\right]f(i)\)。
記 \(\displaystyle h(t,l)=\sum_{i=1}^l\left[i=\prod_{j=t}^mp_j^{c_j},c_j\in\mathbb N\right]f(i)\)，即 \([1,l]\) 中所有隻含 \(p_t,p_{t+1},\dots,p_m\) 質因子的數的 \(f\) 值之和。
Part 2 即為求 \(h(0,n)\)。
邊界 \(h(m+1,l)=1\)，轉移 \(\displaystyle h(t,l)=h(t+1,l)+\sum_{c\in\mathbb N^*}f(p_t^c)\cdot h\left(t+1,\left\lfloor\frac l{p_t^c}\right\rfloor\right)\)。
\(l\) 共有 \(\sqrt n\) 級別種取值，所以直接轉移複雜度為 \(\displaystyle\mathcal O\left(\sqrt n\cdot\frac{\sqrt n}{\ln\sqrt n}\right)=\mathcal O\left(\frac n{\log n}\right)\)，需要優化。
與 \(g\) 的優化方式類似，注意到 \(p_t>l\) 時，能用 \(p_t,p_{t+1},\dots,p_m\) 組成的數只有 \(1\)，此時的 \(h(t,l)=f(1)=1\)。
類似的，推出 \(\forall p_t^2>l,h(t,l)=h(t-1,l)+f(p_t)\)。
所以一旦發現 \(p_t^2>l\) 就停止轉移，記此時的 \(t\) 為 \(t_l\)，之後用到 \(h\) 時，把此時的 \(h\) 值加上 \(\displaystyle\sum_{i=p_{t_l}}^{\min(l,\sqrt n)}[i\in\mathbb P]f(i)\) 即可。
時間複雜度被優化至 \(\mathcal O\left(\dfrac{n^{\frac34}}{\log n}\right)\)。
求和
算出了 Part 1 和 Part 2 的答案，將其相加即為 \(\displaystyle\sum_{i=1}^nf(i)\)。
參考
積性函數線性篩/杜教篩/洲閣篩學習筆記 | Bill Yang's Blog
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Early0v0
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用