min_25筛x学习笔记与相关题目汇总

发表于 | 更新于

$min_{25}$筛专题

本文内容较多。

算法介绍

写在前面的话

$min_{25}$筛是一种可以在亚线性时间复杂度内灵活解决许多种类函数前缀和的算法，一般情况下能做到$10^{10}-10^{11}$的数量级。

我最早在2018年4月，于一次在苏州中学与$xht$闲谈的过程中得知了杜教筛，洲阁筛这类亚线性筛法的存在，由于当时我的竞赛水平较低，便索性将它们归为”目前不需要学习的神仙算法”。这时我还没有听说过$min_{25}$筛。直到2018年的暑假，由于$LibreOJ\ anniversary\ contest\ day3 D$的题解，我才了解到它的存在，但在当时，杜教筛，洲阁筛，$min_{25}$筛这三种筛法在我的脑海中完全没有概念，只是纯粹知道它们的存在而已。

后来，在2018年9月，由于做到了相关题目，我开始学习杜教筛，当时是跟着$jiry_2$的博客学习的，我觉得他写的非常好，不光单纯地罗列出算法的过程，而是用各种例题来试图总结此种算法相关的各种模型，这是我所欣赏的博客。

时光到了2019年的7月，这期间，我试图学习过洲阁筛，但由于当时只是抱着看着玩玩的态度，并没有学会。这几个月间，我大概实战了约$5-10$道的杜教筛题目，印象深刻的有2018年$ACM$徐州网络赛的$D$、$noi.ac$某道冬令营模拟赛的题目，以及2019年5月西安全国邀请赛的$B$题。自认为对于已经学过的杜教筛已经能做到较为熟练的应用。

2019年7月8日，我打开$noi.ac$模拟赛第五场的$T3$,并不会做，打开题解，发现是$min_25$筛，那么，是时候了。

算法过程

大家应当注意，$min_25$筛极其灵活，以下过程只是一个狭隘的经典模板，关键是这种筛法中“埃筛”的思想，这是真正重要的。在下面的应用及例题中我们会发现，实际题目中对算法过程本身进行了极大改动，但“埃筛”的思想是不变的！

我们来求一个函数$f$的前缀和$\sum_{i=1}^nf(i)$

要求：$f(p^c)$可以快速计算，$f$是积性函数。(注意在很多实际题目中，$f$都不是积性函数，这涉及到具体题目中“质因子的贡献”，在不同的题目中千变万化，这里介绍$f$是积性函数只是为了引入经典模型)

比如，$f$是一个$k$次多项式，即相当于$f=\sum_{i=0}^ka_ix^k$,那么相当于对幂函数$id^i$求前缀和并乘上系数即可，后者显然是积性函数。

前$min_25$筛：算法前部

首先我们想求出：$\sum_{i=2}^nf(i)[i\in P]$,注意，在$min_25$筛所有的步骤中，我们的求和下标都从$2$开始，究其根本原因，是因为$min_25$筛的核心思想——埃筛，你见过埃筛从1开始的吗？

回到我们想求的东西，我们考虑在埃筛的时候该怎么求这所有质数的函数和？我们首先应该算出一个总的大表$\sum_{i=1}^nf(i)$,然后我们要把合数的函数值都减掉，考虑埃筛的时候，我们从小到大枚举每个质数$p$,然后把所有$p$的倍数的函数值减掉即可，但是，如果使用真正的埃筛，许多合数会被减去多次，为了使得每个合数的函数值只被减去一次，我们规定一个合数的函数值只能用这个数的最小质因子筛掉，这里又有线性筛的思想。

我们设$P(n)$表示所有小于等于$\sqrt n$的质数所组成的集合，设它们中从小到大的第$i$个为$P_i$,注意，这是$P(n)$的定义，而$P$指的是全体质数集，一定要区分开。显然，要用埃筛去筛掉所有的合数，由于一个合数$x$的最小质因子一定小于等于$\sqrt x$，因此只使用$P(n)$中的质数一定足够将所有合数筛完。

由于我们的最终目的是$\sum_{i=2}^n[i\in P]f(i)$，所以我们实际上不关心合数处$f(x)$取值，然后，我们在使用最小质因子$p_i$来筛$p_ij$的时候，并不能保证$(p_i,j)=1$，因此，我们如果要筛积性函数是有些困难的，但没有关系，我们新造一个函数$F$，满足:

1：$\sum_{i=1}^nF(i)$易于求出

2.$\forall p\in P,f(p)=F(p)$

3.$F$是完全积性函数

事实上，条件$3$不一定需要满足，这里给出条件$3$只是一个经典例子，在做题的时候，只要函数“满足埃筛的某些条件”，则同样可以做。这个$F$函数的选择是算法最灵活巧妙的部分，只有第$1$个条件可能需要略动脑筋。

那么我们求出$\sum_{i=2}^nF(i)$即可

设：$g(n,j)=\sum_{i=1}^n[i\in P\cup p_{min}(i)>p_j]F(i)$表示已经用所有小于等于$p_j$的质数筛完后剩下的函数和。

转移的时候我们直接用$p_j$来筛即可。

$g(n,j)=g(n,j-1)-F(p_j)(g(\lfloor\frac{n}{p_j}\rfloor,j-1)-\sum_{i=1}^{j-1}F(p_i))$

特殊地，如果$p_j^2>n$，则$g(n,j)=g(n,j-1)$。其中设$pre_{j-1}=\sum_{i=1}^{j-1}F(p_i)$，由于$p_i\leq\sqrt n$,直接$O(\frac{\sqrt n}{log\sqrt n})$预处理$pre$即可。

则要求的$\sum_{i=2}^n[i\in P]F(i)=g(n,|P(n)|)$

稍微解释一下，我们筛的值需要满足，最小质因子为$p_j$，对照上面定义式上式应比较显然。

发现$g(x,y)$的$x$是$2\sqrt n$个$\lfloor\frac{n}{i}\rfloor$中的取值，

而$y$有$O(\frac{\sqrt x}{log\sqrt x})$种取值，总的时间复杂度为：

$\int_{1}^{\sqrt n}(\frac{\sqrt x}{log\sqrt x}+\frac{\sqrt \frac{n}{x}}{log\sqrt \frac{n}{x}})dx=O(\frac{n^{\frac{3}{4}}}{logn})$

在实现的时候，我们外层从小到大循环$j$，内层从大到小循环所有预处理出的$\lfloor\frac{n}{i}\rfloor$,即可十分方便地更新，我们就直接把$j$这一维滚动掉了，具体见代码。

后$min_25$筛，算法后部

现在，我们已经有了所有的$g(\lfloor\frac{n}{i}\rfloor,j)$,也就是说，我们只有所有质数的$f$函数和，考虑我们要一个一个把合数的函数值加进来，为了保证每个合数只加一次，我们还是规定每个合数都只能在筛它的最小质因子时被加进来。

设：$S(n,j)=\sum_{i=1}^n[p_{min}(i)\ge p_j]f(i)$即$n$以内所有最小质因子大于等于$p_j$的函数和

我们递推时，首先把$\sum_{i=j}^{|P(n)|}f(p_i)=g(n,1)-pre_{j-1}$，也就是所有质数的函数值加上，然后考虑考虑合数。

显然，如果$p_j^2>n$那么就没有考虑合数的必要了，直接返回即可。

否则，我们直接暴力枚举合数的最小质因子以及最小质因子的次数更新即可，注意，由于$S$函数中不包括$1$，因此实际上所有形如$p^c$的合数都被咕咕了，我们需要特别把它们在后面加上，即：

$S(n,j)=g(n,1)-pre_{j-1}+\sum_{i=j}^{|P(n)|}\sum_{p_i^{e+1}\leq n\cap e>0}f(p_i^e)S(\lfloor\frac{n}{p_i^e}\rfloor,i+1)+f(p_i^{e+1})$

可见，$S(n,1)=\sum_{i=1}^nf(i)$就是我们要求的东西

一般情况下，由于$S(n,j)$的数量可达到$O(\frac{n^{\frac{3}{4}}}{logn})$级别，不方便记忆化搜索，我们直接递归计算。

按照$zbh$的文章：https://zhuanlan.zhihu.com/p/33544708 这里的复杂度为$O(n^{1-\epsilon})$。这也是一般情况下$min_25$筛的复杂度，但尽管如此，这种算法表现出色，一般最大可以应对$10^{11}$的规模

按照$lca$的说法，如果忽略空间复杂度，强行记忆化搜索，时间复杂度为$O(\frac{n^{\frac{3}{4}}}{logn})$,原因未知。

试图写了封装式的板子，不过由于这种筛法过于灵活，因题而异每次都需要改动很多地方：

点击显示/隐藏代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/*
min_25筛模板
by hdmmblz  
loj 6053:简单的函数 
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll MS=100000+5;//最大平方根 
const ll MX=200000+10,mod=1e9+7;//最大平方根的两倍 
ll n;
struct sieve
{
	ll n,pr[MS],fg[MS],cnt=0;
	void sieve_prime()
	{
		int i,j;
		for(i=2;i<=n;i++)
		{
			if(fg[i]==0)
			{
				pr[++cnt]=i;
				fg[i]=i;
			}
			for(j=1;pr[j]<=fg[i]&&1LL*pr[j]*i<=n&&j<=cnt;j++)fg[pr[j]*i]=pr[j];
		}
	}
}s;
ll pow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
struct min_25_pre
{
	ll n,sq,w[MX],m=0,id1[MX],id2[MX],h[MX],g[MX];//后面的h,m为自定义的质数贡献和函数，
	                                              //有的题目需要多个函数结合
	ll km[MX];//各种所需的其他函数（min_25变形较多） 
	ll M(ll a){return a>=mod?a-mod:a;}
	ll add(ll a,ll b){return a>b?0:((a+b)%mod*(b-a+1LL)%mod*pow(2LL,mod-2)%mod);}
	void label()//分类离散化所有的n/i 
	{
		ll i,j;
		for(i=1;i<=n;i=j+1)
		{
			j=n/(n/i);w[++m]=n/i;
			if(w[m]<=sq)id1[w[m]]=m;
			else id2[n/w[m]]=m;
			h[m]=M(w[m]-1+mod);//全程不管f(1),最后再加，这里为初始化g(n/i,0) 
			g[m]=add(2LL,w[m]);
		}	
	}
	void pre_manage(sieve *s)//在筛之前预处理奇怪的函数 
	{
		ll i;km[0]=0;
		for(i=1;i<=(*s).cnt;i++)km[i]=M(km[i-1]+(*s).pr[i]); 
	}
	void manage(sieve *s)
	{
		ll i,j,k,tot,prt;
		tot=(*s).cnt;
		for(i=1;i<=tot;i++)
		{
			prt=(*s).pr[i];
			for(j=1;j<=m;j++)
			{
				if(1LL*prt*prt>w[j])break;
				k=(w[j]/prt<=sq)?id1[w[j]/prt]:id2[n/(w[j]/prt)];
				h[j]=(h[j]-1LL*(h[k]-i+1LL)%mod+mod)%mod;//这里质数的f以及质数f前缀和km需要自定义 
				g[j]=(g[j]-prt*(g[k]-km[i-1])%mod+mod)%mod;
				//printf("%lld %lld %lld %lld %lld\n",i,(*s).pr[i],w[j],h[j],g[j]); 
			}
		}
	}
	void merge(sieve *s)//通常min_25筛在前期是分成很多小函数进行的，因此这里需要合并,这里还用来更新一些其他函数 
	{
		ll i;
		for(i=1;i<=m;i++)
		{
			h[i]=M(g[i]-h[i]+mod);
			if(w[i]>=2)h[i]=M(h[i]+2);//注意合并后很多本次无用的数组是乱的，若下次还要用需要清空 
		}
		km[1]=3;km[0]=0;
		for(i=2;i<=(*s).cnt;i++)km[i]=(km[i]-i+2+mod)%mod;
	} 
	ll solve(ll x,ll y,sieve *s)
	{
		ll ans=0,i,j,tot=(*s).cnt,k,prt,c,prt2;
		if(x<=1||(*s).pr[y]>x)return 0;
		k=(x<=sq)?id1[x]:id2[n/x];
		ans=M(h[k]-km[y-1]+mod)%mod;
		//printf("#%lld %lld %lld %lld %lld\n",x,y,ans,w[k],h[k]);
		for(i=y;i<=tot;i++)
		{
			prt=(*s).pr[i];
			if(1LL*prt*prt>x)break;
			prt2=1LL*prt*prt;
			for(j=prt,c=1;prt2<=x;j=1LL*j*prt,c++,prt2=1LL*prt2*prt)
			{
				ans=(ans+(prt^c)*solve(x/j,i+1,s)%mod+(prt^(c+1)))%mod;//这里的f(p^c)和后部转移需要自定义 
				//printf("%lld %lld %lld %lld %lld\n",x,y,x/j,i+1,ans);
			}
		}
		//printf("%lld %lld %lld %lld\n",x,y,ans,tot);
		return ans;
	}
}a;
int main()
{
	scanf("%lld",&n);
	s.n=sqrt(n);
	s.sieve_prime();
	a.n=n;a.sq=s.n;
	a.label();
	a.pre_manage(&s);
	a.manage(&s);
	a.merge(&s);
	printf("%lld\n",(a.solve(n,1,&s)+1LL)%mod);//最后这一项为f(1) 
	return 0;
}

各种应用分类及典型例题

前言：

我们发现，$f$需要是积性函数？$F$需要是完全积性函数？这些限制其实并不是绝对的。再次重申，$min_{25}$筛的根本思想是埃筛，我们发现我们全程只是在枚举质因子来筛贡献，因此，许许多多的取决于各个或某些特定质因子的函数也可以用此算法来快速计算，它们很多都不是通常意义上的积性函数。

类型1：板题

没什么好说的，跟算法流程描述的一样。

1.1 LibreOJ 6053简单的函数

题目：积性函数$f$满足$f(1)=1,f(p^c)=p\oplus c$，求$\sum_{i=1}^nf(i)$,$n\leq10^{10}$

满足所需的性质：可以快速计算$f(p^c)$，显然除了$f(2)=3$,其他质数$p$均满足$f(p)=p-1$，我们可以直接让完全积性函数$H,F$满足$H(p)=p,F(p)=1$,这两个函数均满足前缀和可直接计算，然后算$g(n,j)$的时候，直接先分别算完基于$H,F$的$g_H,g_F$，然后直接$g=g_H-g_F$，最后，由于$f(2)$的特殊性，让$g(n,1)$最后加上$2$即可，算法前部就完成了。

算法后部直接套上公式就行，非常简单

代码见上面的板子。

类型2：只有次大质因子有贡献的类型

注意：这里的次大质因子以及接下来说的最大/最小都是指不去重的质因子序列，如2·2·3·3的次大质因子为3

在这种情况下，我们可以考虑在算法后部做手脚，我们发现在算法的后部，一个合数的贡献是从按照质因子大小从大到小筛出的（因为我们每一次枚举质因子都保证了这是最小质因子，相当于计算合数的贡献是把质因子从大到小被考虑的结果），那么我们思考一下，对于一个合数，在它被它的次大质因子筛之前，它一定只是一个质数！因此可以考虑算法后部直接在计算质数贡献时让$p_{j-1}$作为次大质因子把贡献乘上，至于合数的贡献我们直接沿用递归的结果即可。清晰地说，我们修改一下$S(n,j)$的定义，表示原来的每个数乘上$p_{i-1}$的贡献和。

形式化地说：$S(n,j)=\sum_{i=1}^n[p_{min}(i)\ge p_j]f(ip_{j-1})$

转移方程即即$S(n,j)=f(p_{j-1})q(n,j)+\sum_{i=j}^{|P(n)|}\sum_{p_i^{e+1}\leq n\cap e>0}S(\lfloor\frac{n}{p_i^e}\rfloor,i+1)+f(p_i)$

其中$q(n,j)$表示$n$以内有多少大于等于$p_j$的质数。

特殊地，我们只要设$p_0=1$，且满足$f(p)$的前缀和可正常计算，则$S(n,1)$即为最终答案。

充分体现了用埃筛处理特殊质因子贡献的思想

2.1.LibreOJ anniversary contest Day3 D

Misaka Network与求和

题目：函数$f$满足$f(1)=0,f(p)=1$,其他情况下$f(x)$表示$x$次大质因子，求：

$\sum_{i=1}^n\sum_{i=1}^nf(gcd(i,j))^k$,$k,n\leq 2·10^9$

先简单莫比乌斯反演一波：

$ans=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2(f^k*\mu)(T)$

直接整除分块，设$g=f^k*\mu$，$g$的前缀和函数为$Sum$，相当于求所有的$Sum(\lfloor\frac{n}{T}\rfloor)$

考虑杜教筛

$g\ast1=f^k\ast\mu\ast1=f^k$

即$Sum(n)=\sum_{i=1}^nf^k(i)-\sum_{i=2}^nSum(\lfloor\frac{n}{i}\rfloor)$

这是一个经典的杜教筛式子，我们只需要求$f^k$的前缀和即可。

如果真的把$p_0$看作$1$，那么$f^k$就是只与次大质因子有关的函数，直接套用上面的模型即可：

点击显示/隐藏代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
/*
min_25筛
by hdmmblz  
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
const ll MS=100000+5;//最大平方根 
const ll MX=200000+10,mod=(1LL<<32);//最大平方根的两倍 
ll n,i,j,kp,ans=0;
struct sieve
{
	ll n,pr[MS],fg[MS],cnt=0;
	void sieve_prime()
	{
		int i,j;
		for(i=2;i<=n;i++)
		{
			if(fg[i]==0)
			{
				pr[++cnt]=i;
				fg[i]=i;
			}
			for(j=1;pr[j]<=fg[i]&&1LL*pr[j]*i<=n&&j<=cnt;j++)fg[pr[j]*i]=pr[j];
		}
	}
}s;
ll pow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
ll M(ll a){return a>=mod?a-mod:a;}
struct min_25_pre
{
	ll n,sq,w[MX],m=0,id1[MX],id2[MX],h[MX],g[MX],mpt[MX]={0},mcx[MX]={0},mpv[MX]={0};//后面的h,m为自定义的质数贡献和函数，
	                                              //有的题目需要多个函数结合
	//ll fu[MX]={0};//各种所需的其他函数（min_25变形较多） 
	//ll add(ll a,ll b){return a>b?0:((a+b)%mod*(b-a+1LL)%mod*pow(2LL,mod-2)%mod);}
	void label()//分类离散化所有的n/i 
	{
		ll i,j;
		for(i=1;i<=n;i=j+1)
		{
			j=n/(n/i);w[++m]=n/i;
			if(w[m]<=sq)id1[w[m]]=m;
			else id2[n/w[m]]=m;
			h[m]=M(w[m]-1);//全程不管f(1),最后再加，这里为初始化g(n/i,0) 
			//g[m]=add(2LL,w[m]);
		}	
	}
	void pre_manage(sieve *s)//在筛之前预处理奇怪的函数 
	{
		ll i;
		mpv[0]=1;
		for(i=1;i<=(*s).cnt;i++)mpv[i]=pow((*s).pr[i],kp); 
	}
	void manage(sieve *s)
	{
		ll i,j,k,tot,prt;
		tot=(*s).cnt;
		for(i=1;i<=tot;i++)
		{
			prt=(*s).pr[i];
			for(j=1;j<=m;j++)
			{
				if(1LL*prt*prt>w[j])break;
				k=(w[j]/prt<=sq)?id1[w[j]/prt]:id2[n/(w[j]/prt)];
				h[j]=M(h[j]-(h[k]-i+(ll)1)+mod);//这里质数的f以及质数f前缀和km需要自定义 
				//g[j]=(g[j]-prt*(g[k]-km[i-1])%mod+mod)%mod;
				//pr**f("%lld %lld %lld %lld %lld\n",i,(*s).pr[i],w[j],h[j],g[j]); 
			}
		}
	}
	/*void merge(sieve *s)//通常min_25筛在前期是分成很多小函数进行的，因此这里需要合并,这里还用来更新一些其他函数 
	{
		ll i;
		for(i=1;i<=m;i++)
		{
			h[i]=g[i]-h[i];
			if(w[i]>=2)h[i]=M(h[i]+2);//注意合并后很多本次无用的数组是乱的，若下次还要用需要清空 
		}
		km[1]=3;km[0]=0;
		for(i=2;i<=(*s).cnt;i++)km[i]=(km[i]-i+2+mod)%mod;
	} */ 
	ll solve(ll x,ll y,sieve *s)
	{
		ll ans=0,i,j,tot=(*s).cnt,k,prt,c,prt2,fu;
		if(x<=1||(*s).pr[y]>x)return 0;
		k=(x<=sq)?id1[x]:id2[n/x];
		if(y==1&&mpt[k])return mpt[k];
		ans=mpv[y-1]*M(h[k]-(y-1)+mod)%mod;
		//pr**f("#%lld %lld %lld %lld %lld\n",x,y,ans,w[k],h[k]);
		for(i=y;i<=tot;i++)
		{
			prt=(*s).pr[i];
			if(1LL*prt*prt>x)break;
			prt2=1LL*prt*prt;
			for(j=prt,c=1;prt2<=x;j=1LL*j*prt,c++,prt2=1LL*prt2*prt)
			{
				ans=(ans+solve(x/j,i+1,s)+mpv[i])%mod;//这里的f(p^c)和后部转移需要自定义 
				//pr**f("%lld %lld %lld %lld %lld\n",x,y,x/j,i+1,ans);
			}
		}
		//pr**f("%lld %lld %lld %lld\n",x,y,ans,tot);
		if(y==1)mpt[k]=ans;
		return ans;
	}
	ll solve2(ll x,sieve *s)
	{
		if(x<=1)return 0;
		ll i,k,ans=0,j;
		k=(x<=sq)?id1[x]:id2[n/x];
		if(mcx[k])return mcx[k];
		ans=solve(x,1,s);
		for(i=2;i<=x;i=j+1)
		{
			j=x/(x/i);
			ans=M(ans-(j-i+(ll)1)*solve2(x/i,s)%mod+mod);
		}
		mcx[k]=ans;
		return ans;
	}
}a;
int main()
{
	ll t;
	scanf("%llu%llu",&n,&kp);
	s.n=sqrt(n);
	s.sieve_prime();
	s.pr[0]=1;
	a.n=n;a.sq=s.n;
	a.label();
	a.pre_manage(&s);
	a.manage(&s);
	//a.merge(&s);
	for(i=1;i<=n;i=j+1)
	{
		j=n/(n/i);
		ans=M(ans+(n/i)*(n/i)%mod*M(a.solve2(j,&s)-a.solve2(i-1,&s)+mod)%mod); 
	}
	printf("%llu\n",ans);
	return 0;
}

类型3：只有最大质因子有贡献

跟刚才想法一样，只有最大质因子有贡献相当于只在算$S$的质数贡献部分考虑贡献即可，合数的贡献都可以直接继承而不需要乘任何系数，相当于枚举最小质因子和次数时乘的系数为$1$，非常简单，也不需要像类型2一样更改$S$的定义

暂时没有例题

类型4：只有最小质因子有贡献

首先必须要保证算法前部的$g$函数可以求出，然后在算法后部递归计算$S$时，只需要单纯的按照$f(x)=1$计算，只有当最后在计算$S(n,1)$时，让枚举最小质因子和次数并乘上$f(p^c)$的贡献即可，因为枚举的$p$保证了是合数的最小质因子，其他的$S(x,y)$只用来求满足条件的数字个数即可。

暂时没有例题

类型5：特定质因子有贡献的题目

特定质因子的个数$m$不会太多（不然没法输入），求$g$时，先按照常规形式的$f$求，然后把这些特殊质数的特殊贡献修改到最后的$g$函数中即可。在求$S$时，只需要在每次枚举质因子是看看这个质因子是常规的还是特殊的并按照正确的贡献乘上对应的系数即可（理解了$min_25$筛的原理这块应该非常显然）。因为本质上这只是相当于不同的质因子有不同的贡献罢了。

5.1 2018ACM-ICPC徐州网络赛D easy math

给定$m\leq2·10^9,n\leq10^{12}$，求$\sum_{i=1}^m\mu(in)$

还记得去年我过这道题的时候就是直接暴力容斥杜教筛，都没算复杂度硬肛一波就过了，那么现在来考虑这个题的$min_25$筛算法。

答案等价于$\mu(n)\sum_{i=1}^nf(i)$，其中$f$是积性函数，满足$f(p^c)=0,c>1,f(p)=-[p\nmid n]$

相当于只有特殊的一些质数的贡献为$0$，其他均为$-1$。我们直接套用上面方法，在求$g$时，暴力把$g$的结果减去$n$以内的特殊质数个数，这里特殊质数是$log(n)$级别可以暴力减，当特殊质数个数较多时，可以预处理特殊质数贡献前缀和并配合二分或数据结构实现查询。

以上是$g$的处理方法，处理$S$时我们同样根据当前枚举的质数是不是特殊质数来决定是否更新即可(特殊质数贡献为0显然无需更新)

点击显示/隐藏代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/*
min_25筛
by hdmmblz  
loj 6053:简单的函数 
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll MS=100000+5;//最大平方根 
const ll MX=200000+10;//最大平方根的两倍 
ll n,m,i,b[MS],cnt=0,mu,tm;
struct sieve
{
	ll n,pr[MS],fg[MS],sp[MS],cnt=0;
	void sieve_prime()
	{
		int i,j;
		for(i=2;i<=n;i++)
		{
			if(fg[i]<=0)
			{
				pr[++cnt]=i;
				if(fg[i]==-1)sp[cnt]=0;
				else sp[cnt]=-1;
				fg[i]=i;
			}
			for(j=1;pr[j]<=fg[i]&&1LL*pr[j]*i<=n&&j<=cnt;j++)fg[pr[j]*i]=pr[j];
		}
	}
}s;
/*ll pow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}*/ 
struct min_25_pre
{
	ll n,sq,w[MX],m=0,id1[MX],id2[MX],h[MX],g[MX];//后面的h,m为自定义的质数贡献和函数，
	                                              //有的题目需要多个函数结合
	ll km[MX];//各种所需的其他函数（min_25变形较多） 
	//ll M(ll a){return a>=mod?a-mod:a;}
	//ll add(ll a,ll b){return a>b?0:((a+b)*(b-a+1LL)%mod*pow(2LL,mod-2)%mod);}
	void label()//分类离散化所有的n/i 
	{
		ll i,j;
		for(i=1;i<=n;i=j+1)
		{
			j=n/(n/i);w[++m]=n/i;
			if(w[m]<=sq)id1[w[m]]=m;
			else id2[n/w[m]]=m;
			h[m]=w[m]-1;//全程不管f(1),最后再加，这里为初始化g(n/i,0) 
			//g[m]=add(2LL,w[m]);
		}	
	}
	void pre_manage(sieve *s)//在筛之前预处理奇怪的函数 
	{
		ll i;km[0]=0;
		for(i=1;i<=(*s).cnt;i++)km[i]=km[i-1]+(*s).sp[i]; 
	}
	void manage(sieve *s)
	{
		ll i,j,k,tot,prt;
		tot=(*s).cnt;
		for(i=1;i<=tot;i++)
		{
			prt=(*s).pr[i];
			for(j=1;j<=m;j++)
			{
				if(1LL*prt*prt>w[j])break;
				k=(w[j]/prt<=sq)?id1[w[j]/prt]:id2[n/(w[j]/prt)];
				h[j]=h[j]-(h[k]-i+1LL);//这里质数的f以及质数f前缀和km需要自定义 
				//g[j]=(g[j]-prt*(g[k]-km[i-1])%mod+mod)%mod;
				//printf("%lld %lld %lld %lld %lld\n",i,(*s).pr[i],w[j],h[j],g[j]); 
			}
		}
	}
	void merge(sieve *s)//通常min_25筛在前期是分成很多小函数进行的，因此这里需要合并,这里还用来更新一些其他函数 
	{
		ll i,j;
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=tm;j++)if(b[j]<=w[i])h[i]=h[i]-1;
			h[i]=-h[i];
			//printf("%lld %lld\n",w[i],h[i]);
			//if(w[i]>=2)h[i]=M(h[i]+2);//注意合并后很多本次无用的数组是乱的，若下次还要用需要清空 
		}
		//km[1]=3;km[0]=0;
		//for(i=1;i<=(*s).cnt;i++)printf("%lld\n",km[i]);
	} 
	ll solve(ll x,ll y,sieve *s)
	{
		ll ans=0,i,j,tot=(*s).cnt,k,prt,c,prt2;
		if(x<=1||(*s).pr[y]>x)return 0;
		k=(x<=sq)?id1[x]:id2[n/x];
		ans=h[k]-km[y-1];
		//printf("#%lld %lld %lld %lld %lld\n",x,y,ans,w[k],h[k]);
		for(i=y;i<=tot;i++)
		{
			prt=(*s).pr[i];
			if((*s).sp[i]==0)continue;
			if(1LL*prt*prt>x)break;
			prt2=1LL*prt*prt;
			//if((*s).sp[i]==0)continue;
			j=prt,c=1;
			if(prt*prt<=x)
			{
				ans=ans-solve(x/j,i+1,s);//这里的f(p^c)和后部转移需要自定义 
				//printf("#%lld %lld %lld %lld %lld\n",x,y,x/j,i+1,ans);
			}
		}
		//printf("%lld %lld %lld %lld\n",x,y,ans,tot);
		return ans;
	}
}a;
int main()
{
	scanf("%lld%lld",&m,&n);
	s.n=sqrt(m);mu=1;
	for(i=2;i*i<=n;i++)
	{
		while(n%i==0)
		{
			if(n/i%i==0)
			{
				printf("0\n");
				return 0;
			}
			mu=-mu;
			if(i<=s.n)s.fg[i]=-1;
			b[++cnt]=i;
			n/=i;
		}
	}
	if(n>1)
	{
		mu=-mu;
		if(n<=s.n)s.fg[n]=-1;
		b[++cnt]=n;
	}
	sort(b+1,b+cnt+1);
	tm=unique(b+1,b+cnt+1)-b-1;
	s.sieve_prime();
	a.n=m;a.sq=s.n;
	a.label();
	a.pre_manage(&s);
	a.manage(&s);
	a.merge(&s);
	printf("%lld\n",(a.solve(m,1,&s)+1LL)*mu);//最后这一项为f(1) 
	return 0;
}

5.2NOI.AC 2019NOI模拟赛第五场T3 签到

题面：一个函数$f$，定义域为$[1,2^{60}]$，满足$f(p^c)=a_c$，其中$a$数组在输入中给出且满足$a_c\in{0,1}$，此函数是一个积性函数，此外，给出$m\leq10^5$个质数$p_i$和一个数字$b$，定义$g(x)=[f(x)=1]\cup[\exists i\leq m,p_i|x]\cup[b|x]$

求$g$前缀和，$n\leq10^{10}$

直接按照第三个条件容斥一下，定义$G(x)=[f(x)=1]\cup[\exists i\leq m,p_i|x]$

则所求为$\sum_{i=1}^n G(i)+\lfloor\frac{n}{b}\rfloor-\sum_{i=1}^{\lfloor\frac{n}{b}\rfloor}G(ib)$

求$G$的前缀和我们可以变成在求$S$时把$S$分成$S(n,j)[0/1][0/1]$表示第一个条件是否满足，第二个条件是否满足的数字个数，然后一样地进行$S$的递归求解即可，至于求后半部分$G(ib)$的前缀和，发现把$b$质因子分解后，相当于在某些特定质因子的某些特定次数上$f(p_i^{c_j})$的值变化了，由于开始的$a$数组只有$logn$个值，每个$b$的质因子最多影响$logn$个$f(p^c)$的位置，也就是说存一张$O(lognloglogb)$的关于$f(p^c)$的表即可，这就是经典的特定质因子特殊贡献，套用上面模型求解即可。