学习笔记 - Min_25筛 | Lucky

还得感谢你用一天的时间竭尽全力准备了这一个半小时
为我免去了找博客的麻烦……

实话实说，这一个半小时对我无益，当然这对你也没有什么影响，出于某种可悲的礼节，又耗费几十秒来写这无所谓的几句话……

# 积性函数前缀和

对于一个积性（不一定完全积性）函数 $f(x)$，求：

$\sum_{i=1}^nf(i)$

解决方法似乎很多，但是这里仅介绍复杂度较为优秀的 Min_25 筛——$O\left(\frac{n^{\frac{4}{3}}}{\log n}\right)$，大概解决 $n\le10^{10}$ 的数据规模。

# 前置

埃氏筛

一个筛质数的筛法，大概思想是枚举质数 $i$，每次删除 $i$ 的倍数。然后有一点优化就是筛去 $i$ 的倍数时，从 $i^2$ 开始枚举，因为 $2$ 到 $i^2$ 的合数已经被之前的质数筛完了。

代码差不多这样：
1
2
3
4
5
6
7
void Function(){
for(int i=2;i<=n;i++){
if(vis[i]) continue; //标记是否被筛掉
for(int j=i*i;j<=n;j+=i)
vis[j]=true; //筛去
}
}

> Tab

对下面会用到的一些符号作一些解释：

$p_i$ 表示第 $i$ 个质数，比如 $p_1=2,p_2=3,p_3=5$；

$P$ 是质数集 $P=\{p_1,p_2,p_3,…\}$；

$l_i$ 表示 $i$ 的最小质因子；

# 函数 $g(a,b)$

在 Min_25 筛中，定义函数 $g(a,b)$ 表示在 $2$ 到 $a$ 的所有满足“最小质因子大于 $p_b$ 或其本身为质数” 的整数 $i$ 的 $f(i)$ 之和。用公式表达即：

$g(a,b)=\sum_{i=2}^a[i\in P\text{ 或 }l_i>p_b]f(i)$

这个函数在后面的计算中会使用，这里先弄懂怎样计算 $g(a,b)$。

我们发现 $g(a,b)$ 表达式中 $[i\in P\text{ 或 }l_i>p_b]=1$ 的 $i$ 就是 埃氏筛用前 b 个质数筛去 1 到 a 之后剩下的数。

因为埃氏筛会留下 1 到 a 的质数。
而对于 1 到 a 的合数 $i$，如果 $l_i\le p_b$，那么就会被 $l_i$ 筛去。

那么可以这样分三种情况考虑递归求解 $g(a,b)$：

如果 $b=0$，那么就是 $\sum_{i=2}^af(i)$；
如果 $a<p_b^2$：注意到埃氏筛中，用 $p_b$ 筛数时是从 $p_b^2$ 开始枚举的——那么 $p_b^2$ 之前的数要么是 $p_b$ 筛不掉，要么是已经被 $p_b$ 之前的质数筛掉了。
所以“用前 b 个质数筛 1 到 a 的数”和“用前 b-1 个质数筛 1 到 a 的数”的结果一样，则 $g(a,b)=g(a,b-1)$。
如果 $a\ge p_b^2$：与情况2 相反，$p_b$ 可以筛掉一些数，那么考虑从“前 b-1 个质数筛剩下的数”中用 $p_b$ 筛一次。
设剩下的数中，$kp_b$ 会被筛去。则有（后面的求和式子就相当于埃氏筛筛去 $p_b$ 的倍数）：
$\begin{split} g(a,b)&=g(a,b-1)-\sum_{k=2}^{\left\lfloor\frac{a}{p_b}\right\rfloor}[l_k\ge p_b]f(kp_b)\\ &=g(a,b-1)-f(p_b)\sum_{k=2}^{\left\lfloor\frac{a}{p_b}\right\rfloor}[l_k\ge p_b]f(k) \end{split}$
于是我们发现满足条件的 $k$ 就是“用前 b-1 个质数筛 $\left\lfloor\frac{a}{p_b}\right\rfloor$”剩下的数中再删去前 b-1 个质数：
$\sum_{k=2}^{\left\lfloor\frac{a}{p_b}\right\rfloor}[l_k\ge p_b]f(k)=g\left(\left\lfloor\frac{a}{p_b}\right\rfloor,b-1\right)-g(p_{b-1},b-1)$
后面 $g(p_{b-1},b-1)$ 其实就是前 b-1 个质数 $p_i$ 的 $f(p_i)$ 之和。所以
$g(a,b)=g(a,b-1)-f(p_b)\left[g\left(\left\lfloor\frac{a}{p_b}\right\rfloor,b-1\right)-g(p_{b-1},b-1)\right]$

这样一个递归的复杂度是 $O\left(\frac{n^{\frac{4}{3}}}{\log n}\right)$ 的。

# 利用函数 $S(a,b)$ 求解答案

- 第一种定义&递归式（记忆化）

定义 $S(a,b)$：

$S(a,b)=\sum_{i=2}^a[i\in P\text{ 或 }l_i\ge p_b]f(i)$

那么答案就为 $S(n,1)+f(1)$。这次我们先给出递归式，再解释。

$S(a,b)=\begin{cases} S(a,b+1)&(a<p_b^2)\\ S(a,b+1)+\sum\limits_{i=1}^{p_b^{i+1}\le a}f(p_b^i)\left[S\left(\left\lfloor\frac{a}{p_b^i}\right\rfloor,b+1\right)-g(p_b,b)\right]+f(p_b^{i+1})&(a\ge p_b^2) \end{cases}$

注意到 $S(a,b)$ 定义式和 $g(a,b)$ 很像——实质上是“用前 b-1 个质数筛 1 到 a 的数”。

如果 $a<p_b^2$，那么在“用前 b-1 个质数筛 1 到 a 的数”筛剩下的数中已经没有可以用 $p_b$ 筛的数了，当然也没有可以用 $p_{b+1}$ 筛的数，因此 $S(a,b)=S(a,b+1)$

反之，$p_b$ 就可以筛掉一些合数，这些被筛去的合数需要被加回来。考虑 $kp_b^i$ 被 $p_b$ 筛去，其中 $k$ 与 $p_b$ 互质，那么 $l_k>p_b$。这里就和 $g(a,b)$ 的求解很像了，我们发现 $k$ 就是“用前 b 个质数筛 $\left\lfloor\frac{a}{p_b^i}\right\rfloor$”剩下的数中再删去前 b 个质数。
注意到最后还加了一个 $f(p_b^{i+1})$——因为合数除了 $kp_b^i$，还有 $p_b^{i+1}$，相当于是特例。

根据我的理解，应该需要递归到 $p_b>a$ 时，此时 $l_i$ 一定小于 $p_b$，那么就只剩质数了。而只剩质数也就是 $g(a,b)$ 在此情况下的定义了。

- 第二种定义&递归式（暴力递归）

重新定义 $S(a,b)$：

$S(a,b)=\sum_{i=2}^a[l_i\ge p_b]f(i)$

也就是去掉了 $i\in P$ 的这种情况。不难发现答案仍然为 $S(n,1)+f(1)$。仍然先给出递归式：

$S(a,b)=\begin{cases} 0&(a<p_b)\\ g(a,+\infty)-g(p_{b-1},+\infty)+\sum\limits_{i=b}^{+\infty}\sum\limits_{t=1}^{p_i^{t+1}\le a}S\left(\left\lfloor\frac{a}{p_i^t}\right\rfloor,i+1\right)f(p_i^t)+f(p_i^{t+1})&(a\ge p_b) \end{cases}$

> Tab.
上面的 $+\infty$ 并不是真的让你把 $i$ 枚举到很大，其实会发现当 $p_i>a$ 时，就可以结束了。$g(a,+\infty)$ 和 $g(p_{b-1},+\infty)$ 同理，只是强调 $l_i$ 一定小于 $p_b$ 而已。

首先第一种为0，比较显然，因为此时 $l_i$ 一定小于 $p_b$。

如果 $a\ge p_b$ 则分两种贡献考虑：

质数的贡献，即计算 $\sum\limits_{i=2}^{a}[l_i\ge p_b\text{ 且 } i\in P]f(i)$。
根据 $g(a,b)$ 的定义，其实就像个前缀和一样，从全部（$g(a,+\infty)$）中减去 $l_i<p_b$ 的（$g(p_{b-1},+\infty)$）。
合数的贡献，就枚举被筛去的数的最小质因数 $p_i$，然后就和“第一种定义&递归式”是一样的了~

这样写不需要记忆化，只要递归到 $p_b>a$ 就行了。（仍然跑的飞快，但是我不会复杂度证明）

The End

Thanks for reading!

“太多的困惑皱起了你的眉尖，太多的失措渐模糊了你的泪眼。不甘心的你，能否把心中的悲伤扑灭——漫天的繁星会照亮你的视野。” -《星愿》