由于Min_25筛过于难学于是又来记笔记了
Min_25筛用于求解次数比较小的多项式积性函数的前缀和。
拿洛谷例题为例：
定义积性函数\(f(x)\),且\(f(p^k)=p^k(p^k-1)\),求\(\sum\limits_{i=1}^nf(i)\)
由于次数比较低我们分次数考虑，下面过程都是在同一次数下进行。
首先按照质数和非质数分类：

\[\sum\limits_{i=1}^{n}f(i)=\sum\limits_{p<=n}f(p)+\sum\limits_{1<=p^e<=n,1<=p<=\sqrt{n}}f(p^e)(\sum\limits_{1<=i<=n/p^e\&\&minp_i>p}f(i)) \]

其中\(minp_i\)表示i的最小质因子。
先看第一部分。
设\(g_k(n,j)=\sum\limits_{i=1}^{n}[i\ is\ a\ prime \ or\ minp>p_j]i^k\)
注意\(i^k\)只在质数处和f取值相同，也就是\(i^k\)是我们构造的一个完全积性函数。
然后考虑\(g(n,i)\)从\(g(n,i-1)\)转移过来，有：

\[g(n,i)=g(n,i-1)-p_i^k(g(n/p_i,i-1)-g(p_{i-1},i-1)) \]

也就是去掉不符合条件的合数，这些合数肯定都是最小质因子等于\(p_i\)的，然后去掉g中包含的质数。
然后注意到后面一项中\(g(p_{i-1},i-1)\)就是前\(j-1\)个质数的k次方和，由于\(p_i<=\sqrt{n}\)所以可以线性筛预处理，设为\(sp_x\)。那么[1,n]中所有质数的k次方和其实就是\(g(n,x)\)，\(p_x\)是最后一个小于等于\(\sqrt{n}\)的质数，记做\(g(n)\).
但是n还是太大了。但是我们又发现 \(\left\lfloor\frac{n}{x}\right\rfloor\)只有\(\sqrt{n}\)级别，可以离散化记录一下分别是谁然后求解，这样的话对每个质数都有\(\sqrt{n}\)次求解，复杂度就是\(\sqrt{n}\times \sum\limits_{i=1}^{\sqrt{n}}[i\ is\ a\ prime]\)。

然后求解答案。设\(f(n,x)\)表示\([1,n]\)中最小质因子大于\(p_x\)的数的f之和，答案就是\(S(n,0)\)
把它分成两部分，一部分是大于\(p_x\)的质数，也就是\(g(n)-sp_x\)，剩下的枚举最小质因子：

\[S(n,x)=g(n)-sp_x+\sum\limits_{p_k^e<=n\&\&k>x}f(p_k^e)(S(\frac{n}{p_k^e},k)+[e!=1]) \]

然后递归求解即可。