Min_25筛

作者: ffacs 分类: 总结 发布时间: 2020-10-03 23:08

Min_25 筛

引入

$O(n^{3/4}/\log n)$ 求一些积性函数的前缀和

质数贡献

我们先求

$$
G(m)=\sum_{i=2}^{m}[i \in prime]f(i)
$$

假设有一个函数 完全积性函数 $f'$ 在质数处与 $f$ 取值相同。我们可以改为求

$$
G(m)=\sum_{i=2}^{m}[i \in prime]f'(i)
$$

还是很难求,我们再改为求

$$
g(k,m)=\sum_{i=2}^m[i\ \in prime\ or\ mpfactor(i)> p[k]]f'(i)
$$

其中, $mpfactor(i)$ 是 $i$ 的最小质因子,$p[k]$ 是第 $k$ 个素数( $2$ 是第一个素数)。 考虑找转移式子。首先,$g(0,m)=\sum_{i=2}^mf'(i)$。,因为 $i$ 最小素因数是小于等于 $\sqrt{i}$ 的,所以当 $p[k]^2>m$ 时,$p[k]$ 不能再筛去任何数字,那么有 $g(k,m)=g(k-1,m)=G(m)$ 。

现在考虑 $p[k]^2 \le m$ 的情况。考虑符合的合数,$g(k,m)$ 比 $g(k-1,m)$ 多筛掉的数即最小质因子等于 $p[k]$ 的数,也就是 $p[k]x$,其中 $x$ 的最小质因子大于等于 $p[k]$ ,即大于 $p[k-1]$。那么就得到转移方程

$$
g(k,m)=g(k-1,m)-f'(p[k])*\left(g(k-1,\left\lfloor \frac{m}{p[k]} \right\rfloor) -\sum_{i=1}^{k-1}p[i] \right)
$$

这里能将 $f'(p[k])$ 提出来就是用了完全积性函数的性质。这个转移方程在 $p[k]^2>m$ 时也满足。我们对就可以进行二维 $\text{DP}$ 了。同时又发现,可以将 $k$ 这一维度优化掉。但是 $m$ 这一维实在太大了。考虑再优化。

首先,我们有恒等式

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

同时,我们的目的是求 $g(k,n)$,可以发现在转移路径上只有 $ \lfloor n/1 \rfloor,\lfloor n/2 \rfloor ,...\lfloor n/n \rfloor$ 这 $O(\sqrt{n})$ 种情况。我们将它们标号即可进行 $DP$。在储存标号时,用 $map$ 就会徒增 $\log n$ 的复杂度,可以将用两个数组存,一个存小于等于 $\sqrt{n}$ 的数的标号,另外一个存 $\lfloor n/x \rfloor(x^2>n)$ 的标号。

这个 $DP$ 的复杂度被证明是 $O(n^{3/4}/\log n)$ 的。那么现在我们就会$O(n^{3/4}/\log n)$ 小于等于 $n$ 的素数前缀和了(取 $f'=f$ )。

前缀和

现在我们有 $G(m)=\sum_{i=2}^{m}[i \in prime]f(i)$ 的贡献了。那么怎么求全部数的贡献呢?

之前求素数的方法启示着我们,可以用 $DP$ 将最小素因子的影响逐步删除。

$$
S(k,m) = \sum_{i=2}^m\left[\ mpfactor(i)>=p\left[ k \right]\ \right] f(i)
$$

对于 $S(k,m)$ 素数部分的贡献就是 $G(m)-\sum_{i=1}^{k-1}f(p[i])$。对于合数,我们枚举最小素因子和它的次数。就有

$$
S(k,m)=G(m)-\sum{i=1}^{k-1}f(p[i])+\sum_{i=k}^{p[i]^2\le n}\sum_{j=1}^{p[i]^{j+1}\le m}\left(f(p[i]^{j})*S\left(k+1,\left\lfloor\frac{m}{p[i]^{j}} \right\rfloor\right)+f(p[i]^{j+1})\right)
$$

这里提取出 $f(p[i]^j)$ 是因为用到了 $f$ 积性函数的特点。

在求 $S$ 的时候我们直接递归不记忆,递归基即 $m<p[j]$,返回 $0$。 这个算法的复杂度被证明同样是 $O(n^{3/4}/\log n)$ 的。

我们要求的前缀和就算出来了,即 $f(1)+S(1,n)$

发表评论

电子邮件地址不会被公开。 必填项已用*标注