Min_25筛学习笔记

简介

Min_25筛是一种积性函数求和的筛法.

因为该算法在 Min_25 使用后才开始普及,因此也被称为 Min_25 筛法.

因为它可以解决一些杜教筛解决不了的东西,所以还是有学习的价值.

条件:

  • $F(x),x \in Prime$可以用多项式表示.
  • $F(x^p),x \in Prime$可以快速计算。

这个条件与洲阁筛相同,但实测比洲阁筛优秀。

有人说洲阁筛应该可以退出积性函数求和的历史舞台了,所以Min_25筛是一个更好的技能。

不会洲阁筛瑟瑟发抖。

没有更多废话的阅读方法

前提

先考虑这么一个问题,对于一个积性函数$F(x)$

要求低于线性复杂度计算
$$
\sum_{i=2}^{n} F(x) \cdot [i \in Prime]
$$
举栗子,$F(i)=i^k$,

那么要求
$$
\sum_{i=2}^{n} i^k \cdot [i \in Prime]
$$
设预处理素数集合$P$,$P$中第$j$个素数是$P_j$

设$g(n,j)$表示在$n$以内,是质数或者最小质因子大于$P_j$的合数的$F$函数值之和
$$
g(n,j)=\sum_{i=2}^{n}i^k \cdot [i\in Prime~~~or~~~Min_{t | i, t \in Prime} > P_j]
$$

  • 对于$P_j>n​$,最小因子是$P_j​$的数是$P_j^2​$,它大于$n​$,说明不会有新的贡献,那么

$$
g(n,j)=g(n,j-1)~~~~~(P_j^2 > n)
$$

  • 对于$P_j \leq n$, 考虑从$g(n,j-1)$到$g(n,j)$的一个转移.

$$
g(n,j)=g(n,j-1)-F(x)\cdot \sum_{x=2}^n[Min_{t|x,t \in Prime}t = P_j]
$$
$g(n,j)$会在$g(n,j-1)$的基础上减去

最小质因子刚好等于$P_j$的数对答案的贡献.

简单来说,后面的$\sum_{x=2}^n[Min_{t|x,t \in Prime}t = P_j]$ 就是最小质因子等于$p_j$的数的个数.

可以把$P_j$提出来,那么要求的是剩下的数中最小质因数仍大于等于$P_j$的那些数的个数.

这个东西就是$g(\frac{n}{p[j]},P_j-1)$,减去小于$P_j$的所有质数的贡献$g(P_j-1,j-1)$

(因为前面的$g(\frac{n}{p[j]})$会多计算小于$p[j]$的质数的贡献)

总结一下,就是
$$
g(n,j)=g(n,j-1) – F(P_j)\cdot [g(\frac{n}{p[j]}, j-1) – g(P_j-1,j-1)]
$$
如果$F(i)=i^k$

那么就是
$$
g(n,j)=g(n,j-1) – P_j^k\cdot [g(\frac{n}{p[j]}, j-1) – g(P_j-1,j-1)]
$$
于是得到了
$$
g(n,j)=
\begin{cases}
g(n,j-1) & &P_j^2> n \
\\
g(n,j-1) – F(P_j)\cdot [g(\frac{n}{p[j]}, j-1) – g(P_j-1,j-1)] && P_j^2 \leq n
\end{cases}
$$

实现细节

我们最后要求的东西就是$g(n,|Prime|)$,这里的$Prime$只需要用到$\sqrt n$.

初始条件
$$
g(n,0)=\sum_{i=1}^{n}F(i)-1
$$

$$
g(P_j-1,j-1)=\sum_{i=1}^{j-1}F(P_j)
$$

因为转移的时候,$g(?,j)$都是从$g(?,j-1)$转移过来的.

那么可以按照$j$作为层次转移,省去$n$那一维.

因为$\frac{n}{p_j}$最多只有$\sqrt n$种,那么转移的时候状态只有$\sqrt n$层.

代码

WGSZOJ 0030 筛法测试(一)

时间复杂度的证明

素数定理:设$\pi (x)$为不超过$x$的素数个数,则$\pi (x)=O(\frac{x}{\ln x})$
$$
\begin{aligned}
&\sum_{i=1}^{\sqrt n} O(\pi(i))+\sum_{i=1}^{\sqrt n}O(\pi (n/i)) \\
&=\sum_{i=1}^{\sqrt n}O(\frac{\sqrt i}{\ln \sqrt i}) + \sum_{i=1}^{n}O(\frac{\sqrt \frac{n}{i}}{\ln \sqrt\frac{n}{i}}) \\
&=O(\int_{1}^{n}\frac{\sqrt{\frac{n}{x}}dx}{\ln n})\\
&=O(\frac{n^{\frac{3}{4}}}{\ln n})
\end{aligned}
$$

前缀和

设$S(n,j)$表示所有最小质因子大于等于$P_j$的$i$的$F(i)$之和
$$
S(n,j)=\sum_{i=1}^{n}F(i) \cdot [Min_{t|x,t \in Prime} t \geq P_j]
$$
首先对于质数的$S$值可以算出

等于
$$
g(n,|p|) – \sum_{i=1}^{j-1}F(P_i)
$$
现在来考虑合数,可以枚举最小质因子为$P_k$,再枚举倍数$e$,满足$P_k^{e+1} \leq n$

合数的贡献可以由积性函数的性质得到

等于
$$
\sum_{k\geq j}^{|P|}\sum_{e}^{P_k^{e+1} \leq n}S(\frac{n}{P_k^e},k+1)F(P_k^e)
$$

这样会算漏$F({P_k}^e \cdot P_k)$的贡献,也就是$F(P_k^{e+1})$,所以把它加上.

得到
$$
S(n,j)=g(n,|p|)-\sum_{i=1}^{j-1}F(P_i)+\sum_{k\geq j}^{|P|}\sum_{e}^{P_k^{e+1} \leq n}(S(\frac{n}{P_k^e},k+1)F(P_k^e)+F(p_k^{e+1}))
$$

这个地方的复杂度我真的不会证,我积分都不会溜了溜了

根据zzq的博客所说,是$\Theta(n^{1-\omega})$的

实现细节

可以通过递归实现或者非递归实现.

根据DoBelieve博客中所述,递归会快与非递归,因为会少遍历一些状态.

但是非递归可以求出$S(a_1,1),S(a_2,1)….$等状态

代码

当$f[i]=1$的时候(输入n,输出n)

练习题

LOJ 6053 简单的函数

分析:

由于$f(p^c)=p \oplus c (p \in Prime)$ ,所以除了$f(2)=3$,其他的$f(Prime_j)=Prime_j-1$.但是$f(i)=i-1$并不是一个积性函数,并不好求.

那么设$g(i)=i$,$h(i)=1$,把这两个积性函数相减就是$f$

那么同样的方法求出$g(n,|p|)$和$h(n,|p|)$,$g(n,|p|)-h(n,|p|)=\sum_{i=2}^n F(i) [i \in prime]$

得到$\sum F(i)$以后就可以通过Min_25的套路求出$S$了.

注意到$f(2)=3$,所以要特判一下加上2.

犯过的错误:

1.线性筛打成maxn.

2.S函数递归的时候调用的是S(n/l,…),事实上应该是S(x/l,…),(点一下跑一年)

3.在S函数中枚举质数的时候没判$pri[j] \times pri[j] \leq x$(wa惨了)

4.调用$dec,pls,mul$函数的时候没有保证传入的参数在模意义下,结果直接爆long long了.(调了一年系列)

常数优化的方法:

1.少取几次模

2.把int和long long换成unsigned long long

3.加一下register

然后就从2000+卡到900+了,但还是没能卡进第一页.

(zzq等神仙的方法太强了,跑得飞快,但是我完全看不懂啊)

参考资料

4 thoughts on “Min_25筛学习笔记”

Leave a Reply

Your email address will not be published. Required fields are marked *