min_25筛模板及应用 / loj6053 / loj6235

前言

在任天洲同学提出洲阁筛的不久后，日本的min_25提出了min_25筛，这两个筛较为相似，而min_25筛相对好写一些，具体筛法可以可以参考min_25的个人博客以及任天洲和朱震霆的集训队论文，和一些博客如min25筛小结。

下面重点讲述一下算法的实现以及应用场景，待求表达式： ∑ i = 1 N f ( i ) \sum_{i=1}^Nf(i) i=1∑N​f(i)其中 f ( i ) f(i) f(i)为积性函数， f ( p ) = p o l y ( p ) ， O ( f ( p k ) ) = O ( 1 ) f(p)=poly(p)，O(f(p^k))=O(1) f(p)=poly(p)，O(f(pk))=O(1)，我们可以看到 f ( i ) f(i) f(i)的前置条件较为宽松，与之对比的杜教筛则需要 f ( i ) f(i) f(i)有能与之配对的 g ( i ) g(i) g(i)，而min_25筛则不必。

min25筛提出了两个辅助函数,分别为 g ( N , j ) = ∑ i = 1 N f ( i ) [ m i n p ( i ) > p j ∣ i ∈ p r i m e ] g(N, j) = \sum_{i=1}^Nf(i)[minp(i)>p_j| i \in prime] g(N,j)=i=1∑N​f(i)[minp(i)>pj​∣i∈prime] S ( N , j ) = ∑ i = 1 N f ( i ) [ m i n p ( i ) ≥ p j ] S(N,j)=\sum_{i=1}^Nf(i)[minp(i) \ge p_j] S(N,j)=i=1∑N​f(i)[minp(i)≥pj​] 那么它们有递推式： g ( n , j ) = { g ( n , j − 1 ) p j 2 > n g ( n , j − 1 ) − f ( p j ) [ g ( n / p j , j − 1 ) − g ( p j − 1 , j − 1 ) ] p j 2 ≤ n g(n,j) = \begin{cases} g(n,j-1) &p_j^2>n \\ g(n,j-1)-f(p_j)[g(n/p_j,j-1)-g(p_j-1,j-1)] &p_j^2 \le n\end{cases} g(n,j)={g(n,j−1)g(n,j−1)−f(pj​)[g(n/pj​,j−1)−g(pj​−1,j−1)]​pj2​>npj2​≤n​ S ( n , j ) = g ( n , ∣ P ∣ ) − ∑ i = 1 j f ( p i ) + ∑ k ≥ j ∑ p k e + 1 < n [ f ( p k e ) S ( n p k e , k + 1 ) + f ( p k e + 1 ) ] S(n,j)=g(n,|P|)-\sum_{i=1}^jf(p_i)+\sum_{k \ge j}\sum_{p_k^{e+1}