本文共 3894 字，大约阅读时间需要 12 分钟。
以前多次学习 Min_25筛，却一直一直不能透彻理解他
这挺让我沮丧的，本来不想写这篇博文，现在看来不写不行
Min_25筛 是用来求解积性函数前缀和的快速筛法
但他对积性函数有一定要求，要求 f ( x ) , x ∈ P r i m e f(x),x\in Prime f(x),x∈Prime 是一个简单多项式，且 f ( x k ) , x ∈ P r i m e f(x^k),x\in Prime f(xk),x∈Prime 可以快速计算
Min_25筛的算法过程分为两步，先求质数的 f ( x ) f(x) f(x) 的和，再求 f ( x ) f(x) f(x) 的和也就是答案。
g ( x ) g(x) g(x) 表示把 x x x 当作质数时计算 f ( x ) f(x) f(x) 得到的结果。
记 G ( i , j ) , i = ⌊ n / d ⌋ G(i,j),i=\lfloor n/d\rfloor G(i,j),i=⌊n/d⌋ 表示在前 i i i 个数中，没有被前 j j j 个质数筛掉数的 g g g 的和。
那么一开始 G ( i , 0 ) = ∑ k = 2 i g ( k ) G(i,0)=\sum_{k=2}^ig(k) G(i,0)=∑k=2ig(k) 。我们要保留的 g g g 都是质数的 g g g ，就要把合数的 g g g 筛走。
从小到大枚举质数 P j P_j Pj ，把最小质因子恰好为 P j P_j Pj 的那些合数的 g g g 从 G G G 中去掉，枚举 ≥ P j 2 \ge P_j^2 ≥Pj2 的 i i i ， G ( i , j ) G(i,j) G(i,j) 要减去 G ′ ( ⌊ i / P j ⌋ , j − 1 ) − ∑ k ≤ j − 1 g ( P k × P j ) G'(\lfloor i/P_j\rfloor,j-1)-\sum_{k\le j-1}g(P_k\times P_j) G′(⌊i/Pj⌋,j−1)−∑k≤j−1g(Pk×Pj) 。 G ′ G' G′ 就是 ∑ g ( i ⋅ P j ) \sum g(i\cdot P_j) ∑g(i⋅Pj) 。
最后的 G ( n , ∣ P ∣ ) G(n,|P|) G(n,∣P∣) 就是质数的 f f f 的和。
F ( i , j ) , i = ⌊ n / d ⌋ F(i,j),i=\lfloor n/d\rfloor F(i,j),i=⌊n/d⌋ 表示表示在前 i i i 个数中，最小质因子 ≥ P j \ge P_j ≥Pj 的 f f f 的和。 F ( n , ∣ P ∣ + 1 ) = 0 F(n,|P|+1)=0 F(n,∣P∣+1)=0 。
因为已经求了 G G G 的答案，现在只需要把合数的 f f f 加上去即可。从大到小枚举 P j P_j Pj ，把最小质因子恰好为 P j P_j Pj 的那些合数的 f f f 加到 F F F 中去，枚举 ≥ P j 2 \ge P_j^2 ≥Pj2 的 i i i ，再枚举 P j e + 1 ≤ i P_j^{e+1}\le i Pje+1≤i 的 e e e ，也就是那些合数中 P j P_j Pj 的指数。 F ( i , k ) , k ≤ j F(i,k),k\le j F(i,k),k≤j, 要加上 f ( P j e ) ⋅ F ( ⌊ i / P j e ⌋ , j + 1 ) + f ( P j e + 1 ) f(P_j^e)\cdot F(\lfloor i/P_j^e\rfloor,j+1)+f(P_j^{e+1}) f(Pje)⋅F(⌊i/Pje⌋,j+1)+f(Pje+1) 。
f f f 的和就是 F ( n , 1 ) + 1 F(n,1)+1 F(n,1)+1 。
G ( i , j ) = { G ( i , j − 1 ) P j 2 > i G ( i , j − 1 ) − G ′ ( ⌊ i / P j ⌋ , j − 1 ) + ∑ k ≤ j − 1 g ( P k × P j ) P j 2 ≤ i G(i,j)= \begin{cases} G(i,j-1) &P_j^2> i \\ G(i,j-1)-G'(\lfloor i/P_j\rfloor,j-1)+\sum_{k\le j-1}g(P_k\times P_j) &P_j^2\le i \\ \end{cases} G(i,j)={ G(i,j−1)G(i,j−1)−G′(⌊i/Pj⌋,j−1)+∑k≤j−1g(Pk×Pj)Pj2>iPj2≤i
F ( n , j ) = ∑ i ≥ j f ( P i ) + ∑ k ≥ j ∑ e f ( P k e ) F ( n / P k e , k + 1 ) + f ( P k e + 1 ) F(n,j)=\sum_{i\ge j}f(P_i)+\sum_{k\ge j}\sum_{e}f(P_k^e)F(n/{P_k^e},k+1)+f(P_k^{e+1}) \\ F(n,j)=i≥j∑f(Pi)+k≥j∑e∑f(Pke)F(n/Pke,k+1)+f(Pke+1)
洛谷的板题