NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. 0. 定义
  2. 2. 1. 用途
  3. 3. 2. 条件
  4. 4. 3. 做法

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 \not= 1]) = f(P_i^t) (h(\lfloor \frac{n}{P_i^t} \rfloor, i + 1) + [t \not= 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 \not=1])}} $$

本文作者 : NekoMio
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接 : https://www.nekomio.com/2019/08/11/154/

本文最后更新于 天前,文中所描述的信息可能已发生改变