min25笔记 | qkoqhh - 什么都没有

前言

之前一直想学。。然后网上博客资料其实也参差不齐，并不是很够很好地吸收。。(其实他们反复提及的东西也确实是 min25 的精髓，只是我没能参透)

然后感谢赵大佬解答了窝的一些疑惑，让窝基本理解 min25 是一个怎样的算法

最后这里应该不会再提及州阁筛的思想了，不过想学 min25 应该先得把州阁筛过一遍(基本理解思想，可以不用实现)

算法流程

1.预处理

准备工作

积性函数中，最重要的是素数，为了求一个积性函数 $f(i)$ 的前缀和，我们先要求 $\sum_p f(p)$ ，即所有素数的函数值的和

这即是 min25 筛的预处理步骤，由于自变量为素数，所以对应的函数形式也比较简单，我们可以以这个函数( min25 筛中要求这个函数为完全积性函数且前缀和比较容易求得 )来进行筛法，将该函数记为 $F(n)$

注意：由于 1 没有最小素因子，min25 筛求解时先暂时忽略 f(1) 的影响

记 $p_i$ 为第 $i$ 小的素数

记 $lpf(n)$ 为 $n$ 的最小素因子

引理 $\forall i\le n$ ，若 $lpf(i)> \sqrt n$ ，则 $i$ 为质数

设

$f(n,j)=\sum_{lpf(i)>p_j||i\in prime}^{i\le n} F(i)$

可以发现 $f(i,j)$ 是在模拟埃式筛法的过程

有引理可以发现，我们只需要将所有小于等于 $\sqrt n$ 的素数筛完即可

记 $m$ 为最大的满足 $p_m\le\sqrt n$

并预处理

$pre(n)=\sum_{i=1}^nF(p_j)$

这里只需要预处理到 $m$ 即可，将在下文筛法中用到

计算

初始状态为

$f(i,0)=\sum_{j=2}^iF(j)$

考虑在当前状态中再筛去 $p_j$ ，即筛去 $\forall lpf(i)=p_j$ ，则有

$f(i,j)=f(i,j-1)-F(p_j)(f(\lfloor\frac{i}{p_j}\rfloor,j-1)-pre(j-1))$

实现时可以考虑按 $i$ 从大到小更新 $f[]$ 数组

复杂度分析

可以发现，如果只是求 $f(n,m)$ ， $i$ 的有效值个数为 $O(\sqrt n)$

另外，用 $p_j$ 更新函数值时，若 $i<p_j^2$ ， $f(i,j)=f(i,j-1)$ 。即 $p_j$ 只会更新 $i\ge p_j^2$ 的函数值

那么考虑个 $i$ 被更新的次数，其复杂度为

$\sum_{i=1}^\sqrt n\frac{\sqrt i}{\ln \sqrt i}+ \sum_{i=1}^\sqrt n \frac{\sqrt \frac{n}{i}}{\ln \sqrt \frac{n}{i}}\le\frac{n^{\frac{3}{4}}}{\ln n}$

2.递归求前缀

求得素数的函数和之后，就能够为求前缀和带来便利

设

$S(n,j)=\sum_{lpf(i)\ge p_j}^{i\le n} f(i)$

和 $f(n,m)$ 的求解相反，我们需要求出 $S(n,1)$

依次枚举最小素因子，可以得到

$S(n,j)=f(n,m)-pre(j-1)+\sum_{k=j}^m(\sum_e^{p_k^e\le n}f(p_j^e)(S(\lfloor\frac{n}{p_j^e}\rfloor,k+1)+\sum_{e=2}^{p_j^e\le n}f(p_k^e))$

这里直接递归即可，不用记忆化

复杂度分析

设复杂度为 $T(n,1)$

$T(n,1)=\sum_{j=k}^m\sum_e^{p_j^e\le n}T(\lfloor\frac{n}{p_j^e} \rfloor,k+1)$

可以发现，到递归到 $S(i,j)$ 时，此时的 $i$ 是 $\lfloor\frac{n}{k}\rfloor$ 的形式，其中 $k$ 是前 $j$ 个素因子的乘积，并且每个满足上述条件的 $k$ 只被计算一次。

另外，当 $i<p_j$ 时，$S(i,j)=0$ ，所以有效的 $i$ 要大于 $p_j$ ，即 $k\le \lfloor\frac{n}{p_j} \rfloor$ ，故复杂度为

这个部分窝还不会证TAT

后记

min25 筛说白了就是简化版的州阁筛，能够处理的是 $f(p)$ 求解难度极其简单的积性函数，例如幂函数。其速度比杜教筛略快，但是作为一个亚线性筛，其处理范围也就在 $10^9\sim10^{11}$ 这个数量级内。

值得一提的是 min25 筛的主要复杂度来自于预处理部分而不是递归部分，据神犇 jlz 的测试，在 $10^{10}$ 的时候，预处理的计算量为 $1.6e7$ ，而递归的计算量接近 $2e5$

另外，如果需要在分块时计算素数的幂函数和，那么一次预处理就可以 $O(1)$ 查询