用途

設$f(x)$是一個積性函數，min_25篩可以在$O(\frac{n^{\frac{3}{4}}}{\log n})$內求$f(x)$的前綴和：${\sum }_{i=1}^{N}f(i)$

使用要求：$f(p),f(p^k)$的值可以快速求出$(p\in Prime)$

算法

Step 1：求${\sum }_{i=1}^n[i\in Prime]f(i)$

約定$P$表示質數集合，$P_i$表示第$i$個質數

首先我們要根據$f(x)$在質數處的點值的表達式構造出$F(x)$（有時需要把$f(x)$拆成多個$F(x)$），滿足 $F(x)$是一個完全積性函數，并且$F(x)$的和可以迅速轉換成$f(x)$的和

然后設$g(n,j)={\sum }_{i=1}^{n}F(i)[i\in Pori的最小質因數>P_j]$

${\sum }_{i=1}^n[i\in P]F(i)$即為$g(n,|P|)$（$|P|$是$P$集合的大小）

考慮$g$的轉移：

若$P_j^2>n$：
顯然不會產生新的貢獻了，此時有$g(n,j)=g(n,j?1)$

若$P_j^2\le n$：
$g(n,j)=g(n,j?1)?\sum [i的最小質因數=P_j]F(i)$
$=g(n,j?1)?F(P_j)\sum [i的最小質因數=P_j]F(\frac{i}{P_j})$
$=g(n,j?1)?F(P_j){\sum }_{k=P_j}^{?\frac{n}{P_j}?}[k的最小質因數>P_{j?1}]F(k)$
$=g(n,j?1)?F(P_j)[g(?\frac{n}{P_j}?,j?1)?g(P_j?1,j?1)]$

關于$g$的初值：

考慮一下$g$的實際含義是什么呢？可以參考一下埃氏篩法的運行過程。

假設現在有$n$個數依次排開，第$i$個數是$f(i)$，根據埃氏篩法的那套理論，每次選出一個質數$p$，然后篩掉所有$f(k\times p)$$(k>=2)$

會發現$g(n,j)$就是運行$j$次埃氏篩法后，沒被篩掉的所有數之和。

這里遞推的起點是$g(n,0)$，$g(n,0)$的含義是把所有的數字當作質數，然后求${\sum }_{i=1}^{n}F(i)$

最后，我們把$F(x)$轉回$f(x)$，
用$g(n,j)$表示${\sum }_{i=1}^{n}f(i)[i\in Pori的最小質因數>P_j]$，
${\sum }_{i=1}^n[i\in P]f(i)$即為$g(n,|P|)$

編碼細節：

轉移$g$只需用到$\sqrt{N}$以內的質數，先線性篩預處理出這些質數

$g$只需要開第一維

題目中的$N$往往很大，$n$直接枚舉的話會炸掉。所以要預處理一個集合$S=\{?\frac{N}{x}?|x\in [1,N]\}$，集合$S$的大小$|S|=2\sqrt{N}$。遞推式中，$?\frac{n}{P_j}?$一定$\in S$，因為$P_j\le \sqrt{N}$，，而所有$\le \sqrt{N}$的數都可以通過$?\frac{N}{x}?$得到，所以$P_j?1\in S$。在具體實現時，先把$S$離散化一下，調用$g$的第一維時，直接枚舉離散化后$S$中各元素的編號。

Step 2：求最終答案

設$S(n,j)={\sum }_{i=1}^{n}f(i)[i的最小質因數>=P_j]$

最終答案即為$S(n,1)+f(1)$

考慮$S$的轉移：

算1~n中質數的貢獻：
$S(n,j)+=g(n,j)?{\sum }_{i=1}^{j?1}f(P_i)$
（${\sum }_{i=1}^{j?1}f(P_i)=g(P_{j?1},j?1)$）

算1~n中合數的貢獻：
$S(n,j)+={\sum }_{k=j}^{P_k^2\le n}{\sum }_{e=1}^{P_k^{e+1}\le n}S(\frac{n}{P_k^e},k+1)\times f(P_k^e)+f(P_k^{e+1})$
（枚舉合數的最小質因數及其最小質因數的指數）

邊界條件：
$if(n<=1||P_j>n)return0;$

編碼細節：

同上，$g$的第一維用離散化后$S$中各元素的編號表示

參考博客：
https://www.cnblogs.com/yoyoball/p/9185144.html
https://blog.csdn.net/baiyifeifei/article/details/90454317
https://www.cnblogs.com/zhoushuyu/p/9187319.html
https://www.cnblogs.com/cjyyb/p/9185093.html

總結

以上是生活随笔為你收集整理的min_25筛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。