【学习笔记】Min25 筛

前言

被各种数论题踩爆了后发现自己不会 $\text{Min25}$ 筛，所以来急救。

正题

$\text{Min25}$ 筛是用于处理特定函数的前缀和的有力方法，一般认为复杂度是 $\mathcal{O}(\dfrac{n^{\frac{3}{4}}}{\log n})$ 或者 $\mathcal{O}(n^{1-\varepsilon})$，实际表现大概可以做 $10^{11}$ 左右，在 $\text{OI}$ 范围内几乎全方位吊打杜教筛（

在本文中，一般认为用 $p$ 表示的数字为质数，$\mathbb{P}$ 表示质数集，$p_x$ 表示第 $x$ 个质数。考虑以下问题：

给定数论函数 $f(x)$ 与 $n$，满足以下条件：

• $f(x)$ 是积性函数。
• $f(x)$ 在任意质数 $p$ 处的取值 $f(p)$ 是关于 $p$ 的低阶多项式。
• $f(x)$ 在 $f(p^e)$ 处的取值易于计算。
  求解：

$$\sum_{i=1}^n f(i)$$
$1\le n\le 10^{11}$。

大体思路

考虑将答案分开计算，分为质数的贡献与合数的贡献，那么：

$$ \sum_{p\in\mathbb{P},p\in[1,n]} f(p)+\sum_{p\notin\mathbb{P},p\in[1,n]} f(p) $$

对于合数，由于函数是积性函数，因此自然地想到取出质数因子，然后两部分相乘一下。那么设 $\text{minp}(x)$ 表示 $x$ 最小质因子，那么考虑取出最小质因子：

$$ \sum_{p\in\mathbb{P}\cap[1,n]} f(p)+\sum_{p^e\in[1,n],p\in[1,\sqrt{n}]} f(p^e)\Big(\sum_{i\times p^e \in[1,n], \text{minp(i)}>p} f(i)\Big) $$

前置数组求解

先考虑计算前面的：

$$ \sum_{p\in\mathbb{P}\cap[1,n]} f(p) $$

这太大了，不能直接筛出来。因此，我们考虑使用一个类似 $\text{dp}$ 的思路来“筛”。

有一天你在梦中突然梦见了这么一个函数 $g(n,x)=\sum_{i=1}^{n} [i\in \mathbb{P}\lor\text{minp}(i)>p_x] f(i)$。

我们发现，上述两个条件实际上只想要第一个，所以考虑带入适当的参数使得第二个条件变得无效。不难发现，当你需要 $[1,n]$ 中质数位置的函数取值和，则可以使用的 $g(n,x)$ 需要满足：$p_x$ 是 $\sqrt{n}$ 以下最大的质数，也就是由于所有 $[1,n]$ 中的合数都不可能存在比 $p_x$ 更大的质因子，所以便不存在合数了。

考虑转移，发现对于固定的 $n$，$x$ 增大，限制变紧了，所以在转移 $g(n,x)$ 的时候，可以在 $g(n,x-1)$ 的基础上减去一些东西。

观察发现，需要减去的东西恰好是 $\text{minp}(s)=p_x$ 的所有合数 $s$ 位置。

那么同样取出一个 $p_x$：

$$ g(n,x)=g(n,x-1)-f(p_x)(g(\dfrac{n}{p_x},x-1)-g(p_{x-1},x-1)) $$

减去 $g(p_{x-1},x-1)$ 是为了减去其中的质数，从而只留下满足条件的合数。

虽然这看起来很厉害，但是存在问题：$g(\dfrac{n}{p_x},x-1)$ 表示接下来质因子都 $\ge p_x$。这意味着接下来可能还有 $p_x$ 这个质因子，那就不能拆出 $f(p_x)$ 了，因为积性函数相乘的时候两边需要互质。

考虑修一下上述对于 $g$ 的定义。由于 $f(p)$ 是一个关于 $p$ 的低阶多项式，所以我们可以拆成若干形如 $f'(x)=x^k$ 的函数，求出他们分别的贡献之后乘上系数求和即可。$f'(x)$ 是完全积性函数，所以令：

$$ g(n,x)=\sum_{i=1}^{n} [i\in \mathbb{P}\lor\text{minp}(i)>p_x] f'(i) $$

$$ g(n,x)=g(n,x-1)-f'(p_x)(g(\dfrac{n}{p_x},x-1)-g(p_{x-1},x-1)) $$

那么上述取出 $p_x$ 的东西就没有问题了，因为 $f'(x)$ 是完全积性的。

但是这函数还是不能直接求，因为 $n$ 实在太大了......不过实际上，我们需要用的 $n$ 是很少的。考虑以下性质：

$$ \left\lfloor\dfrac{\left\lfloor\frac{n}{a}\right\rfloor}{b}\right\rfloor=\left\lfloor\dfrac{n}{ab}\right\rfloor $$

因此所有需要的位置，都可以表示为 $\left\lfloor\dfrac{n}{x}\right\rfloor$ 的形式。根据数论分块，这样的位置个数是 $\mathcal{O}(\sqrt{n})$ 级别！所以就可以存下来，也可以求解了。

存的时候需要注意，要根据 $\left\lfloor\dfrac{n}{x}\right\rfloor$ 中 $x$ 的大小分治一下来存储，保证数组可以只开到 $\sqrt{n}$。

那么 $g$ 数组可以通过滚动数组，枚举每个 $[1,\sqrt{n}]$ 的质数，然后求解。我们设 $g(n)$ 表示 $[1,n]$ 中质数位置取值的和，那么我们就得到了若干个 $g(n)$。

求解答案

得到了 $g(n)$ 之后，便解决了质数部分的求解。再看看柿子：

$$ \sum_{p\in\mathbb{P}\cap[1,n]} f(p)+\sum_{p^e\in[1,n],p\in[1,\sqrt{n}]} f(p^e)\Big(\sum_{i\times p^e \in[1,n], \text{minp(i)}>p} f(i)\Big) $$

使用类似求 $g$ 的方式，令 $S(n,x)=\sum_{i=1}^n[\text{minp}(i)>p_x] f(i)$，那么我们要求的就是 $S(n,0)$。注意到此处的 $x$ 会使得 $p_x\le \sqrt{n}$，因为再大就全是质数了，会直接被 $g$ 给计算到。

得到转移：

$$ S(n,x)=g(n)-\text{sump}(x)+\sum_{k>x,p_k^e\in[1,n]} f(p_k^e)\times\Big(S(\dfrac{n}{p_k^e},k)+[e\ne 1]\Big) $$

先看前面部分：$\text{sump}(x)$ 表示前 $x$ 个质数处函数取值的和。这里不能用 $g$ 是因为可能 $p_x$ 并不能表示为 $\left\lfloor\dfrac{n}{x}\right\rfloor$ 的形式，同时 $x$ 不大，所以 $\text{sump}(x)$ 就是易于计算的了。

再看后面。我们枚举最小质因子和他的次幂，由于我们枚举了次幂，所以可以认为此部分与后面互质，即积性函数可以直接相乘。假设当前是第 $k$ 个质数，那么后面的数字的最小质因子就只能 $>p_k$ 了。

注意一下 $[e\ne 1]$ 的意义。首先，我们发现 $S$ 实际上是不计算 $1$ 的答案的，因此对于 $e>1$，$p^e$ 这个数字本身是合数，但是后面的 $S(\dfrac{n}{p_k^e},k)$ 中又不算他，所以需要 $+1$。但是当 $e=1$，则 $p$ 是质数，已经被 $g$ 中计算了。

剩下的细节

这里 $g$ 和 $S$ 都没有考虑 $1$，因为 $1$ 既不是质数也不是合数，所以需要进行一些特判。

$\text{code}$