0. 定义
$\mathbb{P}$ 表示质数集
1. 用途
Min25筛是一种求积性函数$f(x)$的前缀和$\sum_{i=1}^{N}{f(i)}$的一种方法。
2. 条件
- $f(n)$ 为积性函数 (废话)
- $f(p)$ 在$p$处为关于$p$的低次多项式
3. 做法
首先， 我们定义一个函数$g_k(n, m) = \sum_{i=1}^{n}{i^k[i \in \mathbb{P};or;M(i) > P_m]}$
- 当 $n < P_m^2$ 时 $g_k(n, m) = g_k(n, m - 1)$
- 否则我们要从$g_k(n, m)$中删除$M(i)=P_m$的合数的贡献，也就是
$$\sum_{i=1}^{n}{i^k[i \in \mathbb{C};and;M(i) = P_m]} =P_m^k(g_k(\lfloor\frac{n}{P_m}\rfloor, m - 1)-\sum_{i=1}^{m-1}{P_i^k})$$
之后，我们要计算我们的函数$f(x)$
我们定义$h(n, m)=\sum_{i=1}^n{f(i)[M(i) \ge P_m]}$
先考虑质数，因为$f(p)$ 满足第二个条件， 所以我们可以用$g$函数构造出$f(p)$的答案。
- 那么设$f(p) = \sum{a_k*p^k}$
- 则可以得出$\sum_{i=m}^{|P|}{f(P_i)[P_i<n]} = \sum{a_k*g_k(n, |P|) - \sum_{i=1}^{m-1}{f(P_i)}}$
然后考虑合数
- 枚举合数的最小质因子为$P_i$, 和最小质因子的次数为$t$,
可以将合数写为$P_i^t \times j (M(j) \ge P_{i+1}, j \le \lfloor \frac{n}{P_i^t} \rfloor)$ - 则这些合数的贡献为 $f(P_i^t)((\sum_{j=1}^{\frac{n}{P_i^t}}{f(j)[M(j) \ge P_{i+1}]}) + [t \neq 1]) = f(P_i^t) (h(\lfloor \frac{n}{P_i^t} \rfloor, i + 1) + [t \neq 1])$
- 枚举合数的最小质因子为$P_i$, 和最小质因子的次数为$t$,
综合一下
$$ h(n,m) =\sum{a_kg_k(n, |P|)}-\sum_{i=1}^{m-1}{f(P_i)}+\sum_{i=m}^{|P|}{\sum_{t \ge 1 , P_i^t \le n}{f(P_i^t)(h(\lfloor \frac{n}{P_i^t} \rfloor, i + 1) + [t \neq 1])}} $$