以前多次学习 Min_25筛，却一直一直不能透彻理解他
这挺让我沮丧的，本来不想写这篇博文，现在看来不写不行

Min_25筛
Min_25筛 是用来求解积性函数前缀和的快速筛法
但他对积性函数有一定要求，要求 $f(x),x\in Prime$ 是一个简单多项式，且 $f(x^k),x\in Prime$ 可以快速计算
Min_25筛的算法过程分为两步，先求质数的 $f(x)$ 的和，再求 $f(x)$ 的和也就是答案。

求质数的 $f$ 的和
$g(x)$ 表示把 $x$ 当作质数时计算 $f(x)$ 得到的结果。
记 $G(i,j),i=\lfloor n/d\rfloor$ 表示在前 $i$ 个数中，没有被前 $j$ 个质数筛掉数的 $g$ 的和。
那么一开始 $G(i,0)=\sum_{k=2}^ig(k)$ 。我们要保留的 $g$ 都是质数的 $g$ ，就要把合数的 $g$ 筛走。
从小到大枚举质数 $P_j$ ，把最小质因子恰好为 $P_j$ 的那些合数的 $g$ 从 $G$ 中去掉，枚举 $\ge P_j^2$ 的 $i$ ，$G(i,j)$ 要减去  $G'(\lfloor i/P_j\rfloor,j-1)-\sum_{k\le j-1}g(P_k\times P_j)$ 。$G'$ 就是 $\sum g(i\cdot P_j)$ 。
最后的 $G(n,|P|)$ 就是质数的 $f$ 的和。

求 $f$ 的和
$F(i,j),i=\lfloor n/d\rfloor$ 表示表示在前 $i$ 个数中，最小质因子 $\ge P_j$ 的 $f$ 的和。$F(n,|P|+1)=0$ 。
因为已经求了 $G$ 的答案，现在只需要把合数的 $f$ 加上去即可。从大到小枚举 $P_j$ ，把最小质因子恰好为 $P_j$ 的那些合数的 $f$ 加到 $F$ 中去，枚举 $\ge P_j^2$ 的 $i$ ，再枚举 $P_j^{e+1}\le i$ 的 $e$ ，也就是那些合数中 $P_j$ 的指数。$F(i,k),k\le j$, 要加上 $f(P_j^e)\cdot F(\lfloor i/P_j^e\rfloor,j+1)+f(P_j^{e+1})$ 。
$f$ 的和就是 $F(n,1)+1$ 。

总结
$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}$
$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}) \\$

【LibreOJ #6053】

【JZOJ 5683】【GDSOI2018模拟4.22】

【51NOD 1847】

【51NOD 1965】
我是在 这里 学的