min_25筛学习笔记

参考博客

zsy

xuyixuan

litble

前置

$min_25$ 就是一种能在低于线性复杂度求积性函数 $f(x)$ 前缀和的筛法

复杂度大概为 $O(frac{n^{frac 3 4}}{log_n})$ （不会证，不过朱老大论文里有证明（看不懂））

要求 $f(x)$ 是一个积性函数，而且对于素数 $p$ ， $f(p)$ 和 $f(p^k)$ 可以快速得到

$g$

设 $P$ 表示素数集合, $Min_k$ 表示 $k$ 的最小质因子

$pr_i$ 表示从小到大第 $i$ 个素数

首先考虑求出 $sum_{i=1}^{n}[iin P] f(i)$

定义 $g(n,i)=sum_{j=1}^{n}[jin P{or}Min_j>pr_i] f(i)$

仔细瞪一下这个函数

我们发现从 $g(n,i-1)$ 到 $g(n,i)$

我们就相当于做埃氏筛的过程，用 $pr_i$ 把 $[1,n]$ 所有还没有被筛去的 $pr_i$ 的倍数筛去

实际上 $g(n,i)$ 就是对 $[1,n]$ 用前 $i$ 个素数做一次埃氏筛后剩下的数 $f$ 之和

现在考虑怎么从 $g(n,i-1)$ 推到 $g(n,i)$

首先如果 $pr_{i}^2> n$ 那显然不会有筛去任何数

否则考虑哪些数被删去了

一定是含质因子 $p_i$ ，而且除去 $p_i$ 后最小质因子一定大于 $p_i$

考虑其实也就是减去 $f(p_i) imes g(frac n {p_i},i-1)$

又由于我们把 $pr_1$ ~ $pr_{i-1}$ 这些素数的 $f$ 值减去了，所以要再加一个 $sum_{j=1}^{i-1}f(p_j)$

所以
$g(n,i)= egin{cases} g(n,i-1) && n<p_i^2\ g(n,i-1)-f(p_i) imes[g(frac n{p_i},i-1)-sum_{j=1}^{i-1}f(p_j)] && p_i^2le n\ g(n,i)=n && i=0 end{cases}$

由于最后实际要求的是 $g(n,|P|)$ ，我们只需要开一维就可以了，第二维可以类似滚动数组滚掉

又由于大于 $sqrt n$ 的质因子只有一个

所以我们可以记 $f1[i]$ 表示 $g(i,j)$ ， $f2[i]$ 表示 $g(frac n i,j)$

这样空间复杂度只有 $O(sqrt n)$

代码：当 $f(p)=1$ 即求素数个数时
代码实现比较精细
可以证明这样复杂度是 $O(frac{n^{frac 3 4}}{log_n})$

int lim=sqrt(n);
for(int i=1;i<=lim;i++)f1[i]=i-1,f2[i]=n/i-1;
for(int p=2;p<=lim;p++){
	if(f1[p]==f1[p-1])continue;
	for(int i=1;i<=lim/p;i++)f2[i]-=f2[i*p]-f1[p-1];
	for(int i=lim/p+1;1ll*i*p*p<=n&&i<=lim;i++)f2[i]-=f1[n/i/p]-f1[p-1];
	for(int i=lim;i>=1ll*p*p;i--)f1[i]-=f1[i/p]-f1[p-1];
}
return f2[1];

但是会跑的很慢
你找一照发现问题很简单
卡一下数组枚举和除法以及一些常用变量就会快 $5、6$ 倍

lim=sqrt(n);
for(i=1;i<=lim;++i)f1[i]=i-1,f2[i]=n/i-1,inv[i]=1.0/i;
for(p=2;p<=lim;++p){
	if(f1[p]==f1[p-1])continue;
	x0=f1[p-1],w1=lim/p,w2=min(lim,(n/p/p)),dd=n/p;
	for(i=1;i<=w1;++i)f2[i]+=x0-f2[i*p];
	for(i=lim/p+1;i<=w2;++i)f2[i]+=x0-f1[(int)(inv[i]*dd+1e-7)];
	for(i=lim;i>=1ll*p*p;--i)f1[i]+=x0-f1[(int)(inv[p]*i+1e-7)];
}
return f2[1];