概述:
Min_25筛(aka. 扩展埃氏筛)可以做到在渐进亚线性的时间复杂度下求出大部分数论函数的前缀和.
与杜教筛相比其最大的优点是适用范围广, 符合如下要求的函数$f$均可使用:
- 在质数$p$处的取值是个与$p$有关的项数较小的多项式.
- $f(p^e)$易求.
实现:
抛开$f(1)$, 可以将$S_f(n)=\sum_{i=2}^{n}f(i)$分为质数部分与合数部分:
其中$\mathbb{P}$表示全体素数集合.
Part 1: 质数前缀
首先思考如何求得质数部分的和.
由于前面的条件1, 可以先将多项式拆开, 求得每个幂次的质数部分和再加起来即可.
定义一个函数$g(n,m)$:
其中$\mathrm{LPF}(i)$表示$i$的最小质因子(Least Prime Factor), $P_m$为从小到大的第m个质数, $k$即为分离出来的幂次.
这个函数是整个筛法最精华的部分, 同时也是另一个名字扩展埃氏筛的由来: 这个函数就像是进行了m次埃筛后剩下的部分.
考虑进行dp转移, 有:
其中$S_{P^k}(m-1)$为前$m-1$个质数的$k$次方和, 可以使用线性筛处理.
当$P_m \le \sqrt{n}$时, 此时需要减去最小质因子为$P_m$的数的影响. 由于$i^k$是完全积性函数, 所以可以提出一个$P_m^k$, 同时$g(\lfloor n/P_m \rfloor , m-1)$中还有小于$P_m$的质数部分, 需要减去这部分, 即为$S_{P^k}(m-1)$.
同时根据一个结论:
所以我们只需要求出所有的$g(\lfloor n/i \rfloor)$即可.
存储可以使用根号分治, 使用$idl_x$表示小于等于$\sqrt{n}$的$g(x)$下标, 使用$idh_{\lfloor n/x \rfloor}$表示大于$\sqrt{n}$的$g(x)$下标.
一点点证明: 对于大于$\sqrt{n}$的$x=\lfloor n/i\rfloor$, $\lfloor n/x \rfloor$是唯一的.
由数论分块, 所证即为$i=\lfloor n/ \lfloor n/i \rfloor \rfloor$
Part 2: 合数部分
$[1,n]$中合数的最小质因子一定小于等于$\sqrt{n}$, 对合数部分枚举最小质因子的幂次, 有:
与前面的第一部分类似, 定义函数$S(n,m)$:
则有:
其中$G$即为第一部分求得的各幂次项之和, $m’$是使得$P_{m’}^2\le n$的最大值.
最后所求的前缀和即为$S(n,0)+f(1)$.
时间复杂度:
事实上Min_25筛的时间复杂度比较玄学, 第一部分的时间复杂度使用类似于杜教筛的分析方法可以得到是$O(n^{3/4}/\log n)$. 而第二部分的复杂度是$O(n^{1-\epsilon})$, 且$\epsilon$随$n$增长无限趋近于0(所以是渐进亚线性). 事实上Min_25筛在$10^{11}$内的数据表现良好.
示例代码:
1 |
|