0. 定义#

$\mathbb{P}$ 表示质数集

1. 用途#

Min25筛是一种求积性函数$f(x)$的前缀和$\sum_{i=1}^{N}{f(i)}$的一种方法。

2. 条件#

1. $f(n)$ 为积性函数 (废话)
2. $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])$

• 综合一下

$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])}}$