简介
Min_25筛用来求一个函数的前缀和
如果函数是积性函数就可以做，如果不是积性函数的话有一部分也是可以做的
算法过程就像是在模拟埃氏筛法
时间复杂度是$O(\frac{n^{\frac{3}{4}}}{log(\sqrt{n})})$，然而我并不会证
算法
质数的函数值的前缀和
设$m(x)$表示$x$的最小质因子
假如要求
$$\sum_{i = 1}^{n}f(i)[i是质数]$$
首先将$\sqrt{n}$之内的质数全部筛出来，放在prime数组里
设
$$g(n,j)=\sum_{i = 2}^{n}f(i)[m(i) > prime_j 或 i 是质数]$$
那么
$$
g(n,j) = \begin{cases}
g(n,j - 1) - f(j)[g(\lfloor \frac{n}{prime_j} \rfloor, j - 1) - g(prime_{j - 1}, j - 1)] & prime_j^2 \leq n \
g(n,j - 1) & prime_j^2 > n
\end{cases}
$$
显然，其中的$g(prime_{j-1},j-1)=\sum_{i=1}^{j-1}f(prime_i)$
那么原式中第一维有用的值只有$O(\sqrt{n})$种，预处理即可
最终$g(n,primenum)$就是我们要求的$\sum_{i = 1}^{n}f(i)[i是质数]$
关于$f(x)$
如果只求质数的函数值的话，
$f(x)$应该满足下面几个条件：
若$x$是质数$f(x)$应该要能在$O(1)$内求出来
要能够快速求出$\sum_{i=2}^{n}f’(i)$，其中$f’(i)=\Pi_{j,k}f(j)[k > 0][j^k|n]$
函数值的前缀和
递归版
假设我们要求的函数是$f(x)$，那么问题就是求
$$\sum_{i = 1}^{n}f(i)$$
之前已经求出了
$$\sum_{i = 1}^{n}f(i)[i是质数]$$
的值
那么，现在设
$$h(n,j) = \sum_{i=2}^nf(i)[m(i) \geq prime_j]$$
那么
$$
h(n,j)=g(n,primenum) - g(prime_{i-1},i-1)+
\
\sum_{i=j}^{primenum}\sum_{e\geq 1 且 prime_i^{e+1}\leq n}f(prime_i^e)h(\lfloor \frac{n}{prime_i^e} \rfloor,i+1)+f(prime_i^{e+1})
$$
和上面一样，第一维有用的取值只有$O(\sqrt{n})$种
写一个递归函数，最后的答案即为$h(n,1)+f(1)$
假如就询问没几个$n$的答案，就可以用这种方法
非递归版
这次改变一下状态
设
$$h(n,j)=\sum_{i=2}^nf(i)[m(i)\geq prime_j 或 i是质数]$$
那么
$$
h(n,j)=\begin{cases}
h(n,j+1)+\ \sum_{e \geq 1 且prime_j^{e+1}\leq n}f(prime_j^e)[h(\lfloor \frac{n}{prime_j^e} \rfloor,j + 1) - g(prime_i,i)] + f(prime_j^{e+1})& prime_j^2 \leq n \
h(n,j+1) & prime_j^2 > n
\end{cases}
$$
有没有发现这个式子与质数函数值的前缀和的式子特别像？只不过质数一个是从小枚举到大，一个是从大枚举到小
答案为$h(n,1)+f(1)$
假如要询问许多$n’= \lfloor \frac{n}{x} \rfloor$的答案，就可以用这种方法
关于$f(x)$
$f(x)$函数如果是积性函数，那么应该都可以做
假如不是的话，首先要满足求质数的函数值的前缀和的那些条件
并且若$x=ab,gcd(a,b)=1$，$f(x)$能$O(1)$从$f(a)$和$f(b)$合并，那么应该就能做了（其实我也不是很清楚qaq
关于时间复杂度
暂时还不会。。。