Min25 筛法

简介

min25 筛法可以解决一类积性函数前缀和的问题

$$\sum_{i = 1} ^ n f(i)$$

这样的函数需要满足两个个条件才可以用Min25筛法：

1. 函数是积性函数
2. 形如$f(x^k) [x是质数]$的函数值可以快速求出

算法

我们先考虑算出所有质数的$f(x)$函数的和，也就是素数和减去素数个数

首先我们假设需要求出

$$\sum_{i = 1} ^ n f(i) [i是质数]$$

即小于等于n的素数和

考虑函数$g(n,y)$表示小于等于n的所有数里面是质数或者最小质因子大于$pri_j$的数的和

那么最后需要求出的答案就是$g(n,Psiz)$

考虑g函数怎么转移

当$pri_j^2>n$的时候，显然不会有新的贡献，于是

$$g(n, j) = g(n, j - 1)$$

否则的话我们把最小质因子是$pri_j$的贡献去掉

$$g(n, j) = g(n, j - 1) - f(pri_j)(g(\frac{n}{pri_j}, j - 1) - \sum_{i = 1} ^ {j - 1} f(pri_{i}))$$

因为最小质因子小于$pri_j$的情况我们已经统计过了，所以需要把这些情况减掉
我们可以发现这里的f需要满足是完全积性函数

我们现在算出来了所有质数的$f(x)$的和

那么就可以开始算$f(x)$的前缀和了

设$S(n, j)$表示小于等于n的数里面最小质因子大于等于$pri_j$的所有数的函数和

首先考虑所有质数的贡献

$$S(n, j) = g(n, Psiz) - \sum_{i = 1} ^ {j - 1} f(pri_i)$$

然后枚举和数的最小质因子和其次幂来进行统计

$$S(n, j) += \sum_{i = j} ^ {Psiz} \sum_{e = 1} ^ {pri_i^{e + 1} \le n} f(pri_i^e)S(\frac{n}{pri_i^e}, i + 1) + f(pri_i^{e + 1})$$

这样的算法复杂度是$\frac{n^{\frac{3}{4}}}{\log(n)}$

一般来说可能比杜教快一点？

适用范围比杜教大一些吧

挺好用的一个算法