以前多次学习 Min_25筛，却一直一直不能透彻理解他

这挺让我沮丧的，本来不想写这篇博文，现在看来不写不行

---

Min_25筛

Min_25筛 是用来求解积性函数前缀和的快速筛法

但他对积性函数有一定要求，要求 $f(x),x\in Prime$ 是一个简单多项式，且 $f(x^k),x\in Prime$ 可以快速计算

Min_25筛的算法过程分为两步，先求质数的 $f(x)$ 的和，再求 $f(x)$ 的和也就是答案。

---

求质数的 $f$ 的和

$g(x)$ 表示把 $x$ 当作质数时计算 $f(x)$ 得到的结果。

记 $G(i,j),i=\lfloor n/d\rfloor$ 表示在前 $i$ 个数中，没有被前 $j$ 个质数筛掉数的 $g$ 的和。

那么一开始 $G(i,0)={\sum }_{k=2}^{i}g(k)$ 。我们要保留的 $g$ 都是质数的 $g$ ，就要把合数的 $g$ 筛走。

从小到大枚举质数 $P_j$ ，把最小质因子恰好为 $P_j$ 的那些合数的 $g$ 从 $G$ 中去掉，枚举 $\ge P_j^2$ 的 $i$ ，$G(i,j)$ 要减去 $G^{\prime }(\lfloor i/P_j\rfloor ,j-1)-{\sum }_{k\le j-1}g(P_k\times P_j)$ 。$G^{\prime }$ 就是 $\sum g(i\cdot P_j)$ 。

最后的 $G(n,|P|)$ 就是质数的 $f$ 的和。

---

求 $f$ 的和

$F(i,j),i=\lfloor n/d\rfloor$ 表示表示在前 $i$ 个数中，最小质因子 $\ge P_j$ 的 $f$ 的和。$F(n,|P|+1)=0$ 。

因为已经求了 $G$ 的答案，现在只需要把合数的 $f$ 加上去即可。从大到小枚举 $P_j$ ，把最小质因子恰好为 $P_j$ 的那些合数的 $f$ 加到 $F$ 中去，枚举 $\ge P_j^2$ 的 $i$ ，再枚举 $P_j^{e+1}\le i$ 的 $e$ ，也就是那些合数中 $P_j$ 的指数。$F(i,k),k\le j$, 要加上 $f(P_j^e)\cdot F(\lfloor i/P_j^e\rfloor ,j+1)+f(P_j^{e+1})$ 。

$f$ 的和就是 $F(n,1)+1$ 。

---

总结

$$G(i,j)=\{\begin{array}{ll}G(i,j-1)& P_j^2>i\\ G(i,j-1)-G^{\prime }(\lfloor i/P_j\rfloor ,j-1)+{\sum }_{k\le j-1}g(P_k\times P_j)& P_j^2\le i\end{array}$$

$$F(n,j)=\sum _{i\ge j}f(P_i)+\sum _{k\ge j}\sum _{e}f(P_k^e)F(n/P_k^e,k+1)+f(P_k^{e+1})$$

---

洛谷的板题

#include <bits/stdc++.h>
#define N 1000006
using namespace std;
typedef long long ll;
const ll mod=1e9+7,inv2=5e8+4,inv3=(mod+1)/3;
ll pri[N],num,sp1[N],sp2[N];
ll n,sqr,tot,g[N],gg[N],w[N],id1[N],id2[N];
bool tag[N];
void mo(ll &x){
     x=(x%mod+mod)%mod; }
ll find_pos(ll x){
     return x<=sqr?id1[x]:id2[n/x]; }
void init(ll n){
    
	tag[1]=1;
	for(ll i=1;i<=n;i++){
    
		if(!tag[i]){
    
			pri[++num]=i;
			sp1[num]=(sp1[num-1]+i)%mod;
			sp2[num]=(sp2[num-1]+1ll*i*i)%mod;
		}
		for(ll j=1;j<=num&&pri[j]*i<=n;j++){
    
			tag[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
}
ll S(ll x,ll y){
     // 前 x 个数中，最小质因数大于 pri_y 的数的函数和 
	if(pri[y]>=x) return 0;
	ll k=find_pos(x);
	ll res=(gg[k]-g[k]+mod-(sp2[y]-sp1[y])+mod)%mod,pe,xx;
//	cout<<res<<'\n';
	for(ll i=y+1;i<=num&&pri[i]*pri[i]<=x;i++){
    
		xx=pe=pri[i];
		for(ll e=1;pe<=x;pe=pe*pri[i],xx=pe%mod,e++)
			(res+=xx*(xx-1)%mod*(S(x/pe,i)+(e!=1))%mod)%=mod; //把合法的合数加回来 
	}
//	cout<<res<<'\n';
	return res;
}
int main(){
    
	cin>>n;
	sqr=sqrt(n);
	init(sqr);
	for(ll l=1,r;l<=n;l=r+1){
    
		r=n/(n/l);
		w[++tot]=n/l;
		g[tot]=w[tot]%mod;
		gg[tot]=g[tot]*(g[tot]+1)/2%mod*(2*g[tot]+1)%mod*inv3%mod;
		g[tot]=g[tot]*(g[tot]+1)/2%mod;
		g[tot]--,gg[tot]--;
		if(w[tot]<=sqr) id1[w[tot]]=tot;
		else id2[n/w[tot]]=tot;
	} //初始化 现在的 G 数组表示没有被前 0 个质数筛掉的 g 的和
	
	ll k;
	for(ll i=1;i<=num;i++){
     //筛 
		for(ll j=1;j<=tot&&pri[i]*pri[i]<=w[j];j++){
    
			k=find_pos(w[j]/pri[i]);
			mo(g[j]-=g[k]*pri[i]%mod-sp1[i-1]*pri[i]%mod);
			mo(gg[j]-=pri[i]*pri[i]%mod*(gg[k]-sp2[i-1]+mod)%mod);
		} 
//		cout<<g[1]<<'\n';
	} 
	cout<<(S(n,0)+1)%mod;
}

---

【LibreOJ #6053】
【JZOJ 5683】【GDSOI2018模拟4.22】
【51NOD 1847】
【51NOD 1965】

我是在 这里 学的