Min25 筛

· · 个人记录

Min25 筛

自学成功，前来补充。

首先要认识到，Min25 筛是埃筛的强化版。最神奇的地方在于，式子写出来以后复杂度竟然是对的。

考虑计算积性函数前缀和

F(n)=\sum_{i=1}^nf(i)

Min25 筛的核心思想是，把质数和合数分开算，然后处理合数时通过枚举其最小质因子及其次数来做到。因为合数的最小质因子一定不超过 \sqrt{n}，因此枚举量可以接受。

本篇的讲解顺序可能与其他文章不同，我们先讲 第二部分。

（注：若无特殊说明，下文的所有变量 p 均指质数，p_i 指从小到大第 i 个质数。）

Part 2. 求值

一上来就讲求值，听起来很奇怪。但是由于我学的时候意识到的一些问题，我觉得有必要先引入求值方法再讨论第一部分的 dp 和 Min25 筛的适用范围。我们开始吧。

下文定义 \min_p(i) 为 i 的最小质因子，即 \min_{p|i}p。注意 \min_p(1)=0。

首先，我们把质数和合数分开考虑，其中枚举合数通过枚举其最小质因子及其次数来做到：

F(n)=\sum_{i=1}^{p_i\le n}f(p_i)+\sum_{i=1}^{p_i\le \sqrt{n}}\sum_{e=1}^{p_i^e\le n}f(p_i^e)\left([e>1]+\sum_{2\le j\le\lfloor\frac{n}{p_i^e}\rfloor,p_i<\min_p(j)}f(j)\right)

注意枚举 p_i\le \sqrt{n} 是由上文最小质因子的上界；后面部分可以拆开是因为 f 是积性的，因为枚举了最小质因子，p_i^e 和这个数剩下的部分一定互质，因此可以乘起来；[e>1] 是因为 e=1 的时候是质数本身，已经被算过，防止重复计算。

容易发现最不好搞的是括号里那个东西，我们把它写出来：

S(m,i)=\sum_{2\le j\le m,p_i<\min_p(j)}f(j)

说人话就是最小质因子大于 p_i 的函数值之和。这个东西也可以通过分成质数和合数并枚举合数的最小质因子得到：

\begin{aligned}S(m,i)&=\sum_{k=i+1}^{p_k\le m}f(p_k)+\sum_{k>i}\sum_{e=1}^{p_k^e\le m}f(p_k^e)\left([e>1]+\sum_{2\le j\le\lfloor\frac{m}{p_k^e}\rfloor,p_k<\min_p(j)}f(j)\right)\\&=\sum_{k=i+1}^{p_k\le m}f(p_k)+\sum_{k>i}\sum_{e=1}^{p_k^e\le m}f(p_k^e)\left([e>1]+S(\lfloor\frac{m}{p_k^e}\rfloor,k)\right)\end{aligned}

我们发现这个形式和 F(n) 长得很像。实际上，如果我们记 p_0=0，那么就有 F(n)=S(n,0)+f(1)=S(n,0)+1。因此我们只用考虑 S 的求值即可。

眼尖的同学一眼看出 S(m,*) 中 m 一定是 \lfloor\frac{n}{x}\rfloor 形式，根据整除分块，只有 O(\sqrt{n}) 个不同的值，因此直觉上递归进行后半部分的求和，复杂度是可接受的（注：递归边界为 如果 m\le p_i 那么 S(m,i)=0）。因此瓶颈在于前面那个枚举质数。怎么办呢？

进入到下一部分前，我先列举几个此处可能有的疑问：

  1. 为什么把质数单独拎出来？我去掉前半部分，把后面的式子里的 [e>1] 变成恒定的 +1 不也是正确的吗？
  2. 后面这个东西需要记忆化吗？空间是不是存不下？
  3. 复杂度怎么证？看起来需要枚举很多东西！

我在此处先来回答问题 1，另外两个问题将于复杂度证明部分解答。

答 1：因为后半部分式子的实质是在枚举合数的最小质因子，我们知道这个最小因子最多不会超过 \sqrt{n}。因此 k 的枚举存在一个隐藏上界就是 \pi(\sqrt{n})。如果只考虑后半部分的求和，那么预处理线性筛出 \le\sqrt{n} 的质数就够用了。否则我们需要枚举所有的质数，复杂度显然不能被接受。

那么接着一定会有疑问：为什么把质数单独拎出来的部分复杂度可以接受？这就要回到其他文章所说明的第一部分：质数处点值和。

Part 1：质数处点值和

注意到我们现在想要求这样一个东西：

\sum_{k=i+1}^{p_k\le m}f(p_k)=\sum_{k=1}^{p_k\le m}f(p_k)-\sum_{k=1}^{i}f(p_k)

上文提到后半部分的 k 有一个上界 \pi(\sqrt{n})，注意到 k 同时是式子中递归传入的第二个参数，那么我们可以断言任何被调用的 S(m,i) 中，有 i\le \pi(\sqrt{n})。也就是说 \sum_{k=1}^{i}f(p_k) 是可以在线性筛的时候被预处理的。因此现在我们把注意力放在 \sum_{k=1}^{p_k\le m}f(p_k) 上，也就是质数处点值前缀和。

现在我们放宽限制，如果 f 是完全积性函数，会怎么样？从简单的情况开始：我们考虑另一个完全积性函数 f_c(n)=n^c 在这个质数处点值前缀和中的表现。

Min25 筛在这部分的处理是先求全局前缀和，再不断去掉合数的点值（注意 n=1 处的点值不被计算）。f_c(n)=n^c 的设定下，全局前缀和易于得到（自然数幂和）。在去掉合数的过程中，我们需要一个顺序，仿照前面的思想，我们把这个顺序考虑成最小质因子从小到大。因此我们可以定义一个 g_c(m,i)，满足：

g_c(m,i)=\sum_{k=i+1}^{p_k\le m}f_c(p_k)+\sum_{2\le j\le m,\min_p(j)>p _i}f_c(j)

即全局前缀和去掉 \min_p(j)\le p_i 的合数的点值的和，

$$ \begin{aligned}g_c(m,i)&=g_c(m,i-1)-f_c(p_i)\left(\sum_{2\le j\le \lfloor\frac{m}{p_i}\rfloor,\min_p(j)\ge i}f_c(j)\right)\\&=g_c(m,i-1)-f_c(p_i)\left(g_c(\lfloor\frac{m}{p_i}\rfloor,i-1)-\sum_{j=1}^{i-1}f_c(p_j)\right)\end{aligned} $$ 这里不再枚举次数是因为我知道 $f_c$ 是完全积性的，所以枚举一个即可；同时后面的条件变为 $\min_p(j)\ge i$，允许等于，也是因为我们只是提出一个 $p_i$ 出来，可能还有 $p_i$ 在里面。 减去的东西是因为 $g$ 里包含了前 $i-1$ 个质数，需要去掉。 容易发现这个递推式也仅用到了 $\le \sqrt{n}$ 的质数和整除分块的点值（刚好满足了 Part 2. 的需求），且长的很 dp，因此可以像背包一样压一维递推。复杂度直觉上可以接受。最终需要的是 $g_c(m,\pi(\sqrt{n}))$。 然后我们发现一个事情：**最终的结果是质数处点值的和**。所以如果 $f(p)=\sum_{i\ge 0}a_ip^i$，那么就有 $g(m,\pi(\sqrt{n}))=\sum_{i\ge 0}a_ig_i(m,\pi(\sqrt{n}))$。 这意味着就算我的 $f$ 并不是完全积性的，只需要几个完全积性的 $f_i$ 使得 $f(p)=\sum_{i\ge 0}a_if_i(p)$ 且**能够快速得到全局前缀和**（如 $f$ 是低次多项式），那么一定有 $g(m,\pi(\sqrt{n}))=\sum_{i\ge 0}a_ig_i(m,\pi(\sqrt{n}))$。然后由于 $f_i$ 的完全积性性质，可以用上述方法得到 $g_i(m,\pi(\sqrt{n}))$。至此我们就得到了所有的 $g(m,\pi(\sqrt{n}))$。问题得解。 然后应该有更多的疑问： 4. 仿照 Part 2. 的方法枚举最小质因子次数不行？为什么刚需完全积性？ 5. 我需要证明复杂度！我需要证明复杂度！ 6. Min25 筛的适用范围总结？ 答 4：1. 那你岂不是浪费了完全积性如此美妙的性质，而且不能以 $i$ 作为顺序 dp 了，还得递归（不然存不下）；2. 不然你求全局前缀和不又回原问题了吗？ 答 6：存在几个完全积性的 $f_i$ 使得 $f(p)=\sum_{i\ge 0}a_if_i(p)$ 且**能够快速得到全局前缀和**，快速获得 $\forall p\le \sqrt{n}$ 的 $f(p^e)$。 然后就是复杂度证明！ ### Part 3. 复杂度证明 首先给出结果：Min25 筛的时间复杂度为 $O(\dfrac{n^{\frac{3}{4}}}{\log n})$ 或 $O(n^{1-\epsilon})$。总之是亚线性，实际题目中可以轻松应对 $n\le 10^{10}\sim 10^{11}$。 第一部分：对于 $g_c(m,i)$，一定有 $p_i\le \sqrt{m}$。而 $m$ 的取值是 $1\sim \sqrt{n}$ 和 $n/\sqrt{n}\sim n/1$。每次转移是 $O(1)$ 的，因此复杂度等于枚举量等于： $$ \begin{aligned}&\sum_{i=1}^{\sqrt{n}}\pi(\sqrt{i})+\sum_{i=1}^{\sqrt{n}}\pi(\sqrt{n/i})\end{aligned} $$ 这是 $O(\frac{n^{\frac{3}{4}}}{\log n})$（吧）。 第二部分：被证明为 $O(n^{1-\epsilon})$。