數論：篩子合集
這里主要介紹三種篩子：杜教篩，PN 篩，min_25 篩。
它們可以針對不同特點的數論函數在亞線性的復雜度內求出它的前綴和，即解決如下問題：
給定數論函數 \(f(x)\)，求 \(S(n)=\sum_{i=1}^n f(i)\)，其中 \(n\) 的規模大致在 \(10^9\) 到 \(10^{10}\)。
由于很多地方的計算（比如復雜度）最后一步要用到積分，但是我不會，所以會省略最后積分的步驟。
若無特殊說明 \(p\) 都是質數。
杜教篩
使用條件
可以構造一個數論函數 \(g\)，滿足：
- \(g\) 可以快速求前綴和。
- \(f*g\) 可以快速求前綴和。
注意： 不一定只有積性函數可以用杜教篩求解。
思想
移項，得到：
這就是杜教篩的核心式子。
注意到我們只需要能夠快速求出 \(f*g\) 的前綴和和 \(g\) 的前綴和，就可以用數論分塊遞歸地求出 \(S(n)\) 的值了。
下面是核心代碼：
int S(int n){ //求 S(n)
int l,r,ans=s_fg(n); //s_fg(n) 是 f*g 的前綴和
for(l=2;l<=n;l=r+1){ //數論分塊
r=n/(n/l);
ans-=(s_g(r)-s_g(l-1))*S(n/l); //s_g(n) 是 g 的前綴和
}
return ans/g(1);
}
時間復雜度
我們證明，在使用記憶化搜索之后，上述代碼的復雜度是 \(O(n^{\frac{3}{4}})\)。
引理： 記 \(R(n)=\{ \lfloor \frac{n}w0obha2h00 \rfloor | 2\le d\le n\}\)，則任意的 \(x\in R(n)\) 都滿足 \(R(x)\subseteq R(n)\)。
證明：設 \(x=\lfloor \frac{n}{i} \rfloor\)，則 \(y\in R(x)\) 滿足 \(y=\lfloor \frac{x}{j} \rfloor=\lfloor \dfrac{\lfloor \frac{n}{i} \rfloor}{j} \rfloor\)=\lfloor \frac{n}{ij} \rfloor \in R(n)$。
這意味著，使用記憶化搜索以后，要求的不同的 \(S(x)\) 只有 \(|R(n)|=O(\sqrt{n})\) 種。
省去遞歸調用的時間，因為求每個 \(S(x)\) 時數論分塊需要 \(O(\sqrt{x})\) 地遍歷，所以求 \(S(n)\) 的總復雜度 \(T(n)\) 是：
進一步的，我們可以提前預處理 \(x\le m\)（\(m\ge \lfloor \sqrt n \rfloor\)） 時 \(S(x)\) 的答案（當然如果 \(f\) 的性質不是很好可能沒法預處理），那么復雜度變成：
如果預處理的復雜度是 \(O(m)\)（比如 \(f\) 是積性函數時可以線性篩），那么平衡得最優復雜度是 \(O(n^{\tfrac{2}{3}})\)。
實現細節
如果使用 unordered_map 或者哈希表存儲結果來記憶化，常數會有點大，我們考慮不用哈希表。具體地，我們開一個數組 dp 記錄答案，并取一個閾值 \(B=\lfloor \sqrt{n} \rfloor\) ：
- 如果 \(x\le B\)，就把 \(S(x)\) 存到
dp[x]中。 - 否則，就把 \(S(x)\) 存到
dp[B+n/x]中。
注意： 如果使用的是 \(O(n^{\frac{2}{3}})\) 的寫法，\(x\le B\) 的答案已經預處理好了，可以不用管。
接下來我們證明不會出現兩個 \(x,y\in R(n)\) 他們用的是 dp 的同一個位置。
證明：\(\le B\) 的情況顯然不會出問題，我們只需要證明 \(x,y>B\) 的情況即可。
假設 \(x\ne y\) 但是 \(\lfloor \frac{n}{x} \rfloor=\lfloor \frac{n}{y} \rfloor\)，我們設 \(x=\lfloor \frac{n}{i} \rfloor,y=\lfloor \frac{n}{j} \rfloor\)。
那么有 \(\lfloor \tfrac{n}{\lfloor \tfrac{n}{i} \rfloor} \rfloor=\lfloor \tfrac{n}{\lfloor \tfrac{n}{j} \rfloor} \rfloor\)，這意味著 \(i,j\) 屬于同一個塊（因為他們所屬塊的右端點一樣），從而必有 \(\lfloor \frac{n}{i} \rfloor = \lfloor \frac{n}{j} \rfloor\)，這與 \(x\ne y\) 矛盾了，所以不會出現這種情況。
所以這樣存儲是正確的。
應用
(1). 求 \(\mu\) 的前綴和。
取 \(f=\mu,g=1\)，則 \(f*g=\mu*1=\epsilon\)，顯然可以快速求出 \(1,\epsilon\) 的前綴和。
(2). 求 \(\varphi\) 的前綴和。
取 \(f=\varphi,g=1\)，則 \(f*g=\varphi*1=id\)，顯然可以快速求出 \(1,id\) 的前綴和。
(3). 求 \(\mu \cdot id_k,\varphi \cdot id_k\)
處理這類帶點乘的式子有一個技巧，就是根據 \((A\cdot C)*(B\cdot C)=(A*B)\cdot C\)（證明直接展開即可），比如對于上面這兩個東西可以這樣處理，取 \(g=id_k\)：
- \((\mu \cdot id_k) * id_k = (\mu \cdot id_k) * (1 \cdot id_k) = (\mu*i)\cdot id_k = \epsilon \cdot k =\epsilon\)。
- \((\varphi \cdot id_k) * id_k = (\varphi \cdot id_k) * (1 \cdot id_k) = (\mu*i)\cdot id_k = id \cdot id_k = id_{k+1}\)。
給兩道典題：
PN 篩
使用條件
- \(f\) 是積性函數。
- 存在一個函數 \(g\) 使得：
- \(g\) 是積性函數。
- \(g\) 在質數 \(p\) 上的取值和 \(f\) 相等，即 \(f(p)=g(p)\)。
- \(g\) 易求前綴和，下面設 \(G(n)\) 表示 \(g\) 的前綴和。
思想
Powerful Number（PN）
先介紹什么是 PN。
定義：若 \(n=\prod p_i^{c_i}\) 滿足 \(\forall i，c_i\ge 2\)，則 \(n\) 是一個 Powerful Number，簡稱 PN。
性質一： 任何一個 PN 都可以表示成 \(a^2b^3\) 的形式。
證明：依次考慮每個質因子，若指數是偶數就放到 \(a\)，否則先把 \(3\) 個放到 \(b\) 其余的放到 \(a\)。
性質二： \(n\) 以內的 PN 只有 \(\sqrt{n}\) 個。
證明：考慮枚舉 \(a\) 并計算滿足條件的 \(b\) 的個數，之后積分可證。
由性質二我們要找出所有 PN 的話只需要 dfs 枚舉每個指數的因數就可以了。
PN 篩
他的思想和杜教篩有點像。
由于 \(f,g\) 是積性函數，所以必定存在一個數論函數 \(h\) 滿足 \(f=g*h\)（或者說 \(h=f/g\)，逆元是在狄利克雷卷積意義下的），且 \(h\) 也是積性函數。
那么 \(f(p)=g(1)h(p)+g(p)h(1)=h(p)+g(p)\)，而因為 \(f(p)=g(p)\)，所以 \(h(p)=0\)，而又因為 \(h\) 是積性函數，所以 \(h\) 在所有非 PN 數處的取值都是 \(0\)。
我們有：
因為上面我們證明了 \(h\) 僅在 PN 處有值，所以上面有用的 \(d\) 只有 \(O(\sqrt{n})\) 個，也就是說我們只需要在每個 PN 處計算 \(h(d)G(\frac{n}w0obha2h00)\) 并累加到答案里即可，而因為 \(h\) 是積性函數，所以我們如果知道每個 \(h(p^k)\) 的值，就可以在 dfs 搜索 PN 的過程中計算出 \(h(d)\)。
求 \(h(p^k)\) 一般是兩種求法，一種是根據定義式 \(h=f/g\) 推導出 \(h\) 的通項公式，這種比較吃操作而且因題目而異，主要介紹令一種不太吃手法的方法：
因為 \(f(p^k)=\sum_\limits{c=0}^k g(p^c)h(p^{k-c})\)，所以 \(h(p^k)=f(p^k)-\sum_\limits{c=1}^{k} g(p^c)h(p^{k-c})\)，可以直接枚舉 \(c\) 進行計算。
時間復雜度
先看預處理 \(h(p^k)\) 的復雜度（如果你用第一種做法那顯然不需要預處理）。
因為 \(p\) 只需要處理到 \(\sqrt{n}\)（更大的質數不可能作為 PN 的質因數），而 \(\sqrt{n}\) 以內的質數約有 \(O(\frac{\sqrt{n}}{\log n})\) 個，每個質數的指數不超過 \(\log n\)，算的時候要 \(O(k)\) 枚舉，所以這部分的復雜度是 \(O(\sqrt{n} \log n)\)，但是肯定跑不滿。
再看 dfs 搜索 PN 累加答案的復雜度，由于 PN 的個數是 \(O(\sqrt{n})\) 個，所以如果 \(G\) 可以 \(O(1)\) 求那么復雜度就是 \(O(\sqrt{n})\)。
實現細節
搜索 PN 的 dfs 不要寫假了。
例題
因為 \(f(p)=p(p-1)\)，所以我們可以取 \(g(n)=n\varphi(n)\)，顯然他是積性函數。
我們可以用杜教篩求 \(g\) 的前綴和，然后上 PN 篩即可。
此時復雜度瓶頸在于杜教篩，總復雜度為杜教篩的 \(O(n^{\tfrac{2}{3}})\)。
Tip：這題實際上可以得到 \(h(p^k)=p^k(p-1)(k-1)\)。
OK 簡單的講完了，現在要開始講最麻煩的 min_25 了。
min_25 篩
使用條件
- \(f\) 是積性函數。
- \(f(p)\) 是關于 \(p\) 的簡單多項式，一般次數不超過 \(10\)。
- \(f(p^k)\) 可以快速求值。
思想
min_25 篩分為兩個部分。
質數的 \(c\) 次冪前綴和
我們先解決一個問題，給定 \(n\)，如何求 \(n\) 以內的所有質數的 \(c\) 次冪的和。
我們約定：
- \(mn(x)\) 表示 \(x\) 的最小質因子，特殊的，\(mn(1)=+\infty\)（注意 \(mn(1)\) 不是 \(0\)！）。
- \(p_i\) 表示第 \(i\) 小的質數。
- \(p_m\) 是最大的 \(\le \sqrt{n}\) 的質數。
- \(P_k\) 表示前 \(k\) 個質數構成的集合。
模仿線性篩的思路，在一個合數的最小質因子處把他篩去，由于一個合數必然有一個 \(\le \sqrt{n}\) 的質因子，所以我們只需要把質數處理到 \(\sqrt{n}\) 就可以篩完所有的合數。
設 \(S(n,k)=\left\{ x | 1\le x \le n,mn(x)>p_k \right\}\) 表示處理完了前 \(k\) 個質數，前 \(n\) 個數中沒被篩去的數的集合（根據約定 \(1\) 一定屬于 \(S(n,k)\)），并設 \(h(n,k)=\sum_{x\in S(n,k)} x^c\)，則 \(h(n,m)-1+\sum_\limits{i=1}^m p_i^c\) 就是答案。
記 \(D(n,k)=\left\{ x | 1\le x \le n,mn(x)=p_k \right\}\) 表示第 \(k\) 輪刪去的數的集合，那么根據定義有 \(S(n,k)=S(n,k-1)-D(n,k)\)。
一個顯然的事情是如果一個數在第 \(k\) 輪被刪除，設它是 \(p_k\cdot x\)，那么 \(x\le \lfloor \frac{n}{p_k} \rfloor\)，并且 \(x\) 在前 \(k-1\) 輪沒被刪掉，即 \(x\in S(\lfloor \frac{n}{p_k} \rfloor,k-1)\)。同時，如果一個數 \(x\in S(\lfloor \frac{n}{p_k} \rfloor,k-1)\)，那么 \(p_k\cdot x\) 一定會在第 \(k\) 輪被刪掉。所以這就構成了一個雙射，于是我們得到了：\(D(n,k)=p_kS(\lfloor \frac{n}{p_k} \rfloor,k-1)\)。
再帶回到上面那個式子就得到了 \(S\) 的遞推式：\(S(n,k)=S(n,k-1)-p_kS(\lfloor \frac{n}{p_k} \rfloor,k-1)\)，進一步可以推出 \(h\) 的遞推式：\(h(n,k)=h(n,k-1)-p_k^c h(\lfloor \frac{n}{p_k} \rfloor,k-1)\)。
邊界是 \(h(n,0)=\sum_{i=1}^n i^c\)，可以直接拉插求出自然數冪和。
如果直接用這個遞推式去做，那么第一維是 \(O(\sqrt{n})\) 的，第二維是 \(O(\frac{\sqrt{n}}{\log n})\) 的，于是我們得到了一個 \(O(\frac{n}{\log n})\) 的完全過不去的做法。
注意到我們現在的答案是 \(h(n,m)-1+\sum_\limits{i=1}^m p_i^c\)，不太美觀，考慮設 \(S'(n,k)=S(n,k)\cup P_k\)，\(h'(n,k)=\sum_{x\in S'(n,k)} x^c\)，那么答案就變成了 \(h'(n,m)-1\)。
并且 \(S'\) 有一個很好的性質：根據我們一開始的分析，當 \(p_k>\sqrt{n}\) 時，\(p_k\) 無法篩掉除了自己之外的任何數，所以 \(S'(n,k)=S'(n,k-1)\)。
仍然和上面一樣我們去求出 \(S'\) 的遞推式：
同理，\(h'\) 的遞推式為：
雖然看著和 \(h\) 好像是一樣的，但是因為當 \(p_k>\sqrt{n}\) 時，\(S'(n,k)=S'(n,k-1)\)，所以對于每個 \(x\) 的 \(h'(x,k)\) 第二維的 \(k\) 是 \(O(\frac{\sqrt{x}}{\log x})\)（原先不管 \(x\) 是什么第二維始終是 \(O(\frac{\sqrt{n}}{\log n})\)）的，那么復雜度就變成了 \(O(\tfrac{n^{\frac{3}{4}}}{\log n})\)。
會發現我們實際上得到了所有 \(\lfloor \frac{n}{i} \rfloor\) 的答案。
積性函數前綴和
現在我們要求一個滿足開頭的使用條件的積性函數 \(f\) 的前綴和。
借鑒第一部分的思想，設 \(g(n,k)=\sum_\limits{1\le x\le n,mn(x)\ge p_k} f(x)\)，轉移考慮枚舉 \(x\) 的最小質因子 \(p_t\) 并枚舉他的指數 \(c\)，則：
顯然當 \(p_t> \sqrt{n}\) 時，符合條件的 \(x\) 只有 \(p_t\) 一個，所以我們枚舉 \(p_t\) 只需要枚舉到 \(\sqrt{n}\)，對于 \(>\sqrt{n}\) 的質數用我們第一部分預處理出來的東西算即可。
復雜度可以視為 \(O(\tfrac{n^{\frac{3}{4}}}{\log n})\)，證明我不會，可以看原論文。
實現細節
- 預處理 \(h'\) 的時候因為我們只需要用最后的東西，所以可以把 \(k\) 這一維滾掉，減少時空常數。
- min_25 篩的搜索過程可以不用記憶化。
例題
I. 【模板】Min_25 篩
板子，不多講了
II. 簡單的函數
當 \(p=2\) 時 \(f(p)=p+1\)，其他情況都有 \(f(p)=p-1\)，所以特殊處理一下 \(2\) 的情況直接上 min_25 即可。
III. 【UR #13】Sanrd
嚴格來講這題只是用到了 min_25 的思想。
設 \(f(x)\) 表示 \(x\) 的非嚴格次大質因子（\(f(1)=0\)），相當于求這個東西的前綴和。
仍然考慮設 \(S(n,k)\) 表示 \(\le n\) 且最小質因子 \(\ge p_k\) 的數構成的集合，思考在上面的遞推式中如果把 \(x\in S(\lfloor \tfrac{n}{p_t^c} \rfloor,t+1)\) 乘上 \(p_t^c\) 會發生什么：
- \(x\) 是合數：\(f(x\times p_t^c)=f(x)\)。
- \(x\) 是質數：那么 \(f(x\times p_t^c)=p_t\)。
- \(x=1\)：\(f(x\times p_t^c)=[c\ge 2]\cdot p_t\)。
根據這個直接做即可。
由于質數在這題中不產生貢獻，所以我們都不需要做第一部分。
浙公網安備 33010602011771號