【学习笔记】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}$

添加新评论