「末世追忆」：“临近深渊的时刻，钟表将停止转动。”
申明
本文中提及的 在无特殊说明的前提下皆表示质数。
筛质数
首先明晰质数的概念，即一个数 仅能被 和其本身整除。
埃氏筛
对于任意一个非质数一定存在 使得 。那么，我们可以通过枚举每一个数的质因数来使其被筛掉，但如果我们对于每一个 都去筛一遍的话，时间复杂度依然会高达 ，这个通过积性分析得到： 。
但我们并不能满足于此，这样只能至多筛出 的质数。我们记录一个 来表示是否是质数。同样按照质因数筛的思路，如果我们已经判断了某一个数 不是质数，我们就不需要去筛这个数了，因为这个数也是被一个比它小的质因数筛掉的，根据数论基本定理，如果 ，则 ，所以 的所有倍数也都已经被筛过了。
这种筛法被称为埃氏筛。时间复杂度为 。
一般实现
1
2
3
4
5
6
7
8
9
10
11
| int pri[MAXN],Tot;
bool is[MAXN];
inline void sieve(int n)
{
for(int i=2;i<=n;++i)
{
if(is[i]) continue;
pri[++Tot]=i;
for(int j=i+i;j<=n;j+=i) is[j]=1;
}
}
|
线性筛
我们在埃氏筛之上进行优化，使其真正达到线性的复杂度。分析埃氏筛的实现过程，容易发现，每一个非质数都会被自己的每一个质因数筛一遍。
我们原本的数列如下表示：
然后我们筛掉质数 ，则表示为：
然后筛质数 ：
容易发现， 被筛了两次，之后这种现象还会屡次出现，降低了我们筛质数的效率。
我们考虑如何优化使得任意一个合数只会被自己最小的质因数筛掉，直觉和分析都告诉我们，这种做法的时间复杂度为 的线性。
考虑用如下方式来表示合数集合：
也就是用质因数分解的方式来表示合数，那同样的，我们要可以用枚举质数的方式来筛合数，那如何保证不漏呢。
设当前枚举数为 ，而我们当前拥有的质数集合也满足了 ，如果我们枚举质数集合，会使 内所有包含 个质因数的合数都被筛掉。也就是，我们以任意数为底，并将其乘以一个质数作为合数筛掉，仔细想想，这绝对是保证了不漏的。
但事实上，这样依然会有数被重复筛，所以考虑添加优化。令当前底数为 ，枚举的质数集合为 ，当 的时候，容易发现，由于我们是由小到大枚举的质数集合，则我们枚举到的第一个满足 的 就是 的最小质因数，而根据我们前面推断的优化方案，在这个时候，我们就可以停止对底数 的筛了。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| bool is[MAXN],pri[MAXN],tot;
inline void sieve(int n)
{
memset(is,1,sizeof(is));
is[1]=0;
for(int i=2;i<=n;++i)
{
if(is[i]) pr[++tot]=i;
for(int j=1;j<=tot&&i*pri[j]<=n;++j)
{
is[i*pri[j]]=0;
if(i%pri[j]==0) break;
}
}
}
|
有意思的练习题
这道题有够水的，甚至于 都能勉强卡过。
不过我们还是先一遍线性筛，然后二分查找第一个比 大的质数。
时间复杂度 ，其中 。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| while(N)
{
if(Is[N]) puts("0");
else
{
int l=1,r=Tot;
while(l<r)
{
int mid=(l+r)>>1;
if(Pri[mid]>N) r=mid;
else l=mid+1;
}
write(Pri[l]-Pri[l-1]),puts("");
}
read(N);
}
|
最优的筛法并不一定最优。
这道题，如果使用欧拉筛的话，每一个数只会被自己最小的质因子筛掉。而我们的 可以是任一质因子。考虑埃氏筛。
埃氏筛保证每一个数都会被自己的所有质因子筛到。所以我们直接求取 的所有质数，并在其中处理满足 条件的，并把它们在并查集中合并。
令当前质数为 ，我们枚举 ，显然， 和 有一个质因子为 ，所以 和 必在一个集合。所以我们扫一遍，然后把上述的两个连在一起就好了。
时间复杂度如果我没记错的话，是 。
参考代码
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
| bool Is[MAXN];
int a,b,p,Fa[MAXN];
int Anc(int x)
{
return Fa[x]==x?x:Fa[x]=Anc(Fa[x]);
}
inline void Sieve(int n)
{
for(int i=2;i<=n;++i)
{
if(!Is[i])
if(i>=p)
{
for(int j=i<<1;j<=n;j+=i)
{
Is[j]=1;
if(j-i>=a&&Anc(j)!=Anc(j-i))
Fa[Anc(j)]=Fa[Anc(j-i)];
}
}
else for(int j=i<<1;j<=n;j+=i) Is[j]=1;
}
}
int main()
{
read(a,b,p);
for(int i=a;i<=b;++i) Fa[i]=i;
Sieve(b);
int ans=0;
for(int i=a;i<=b;++i) if(Fa[i]==i) ++ans;
write(ans);
return 0;
}
|
线性筛/欧拉筛
在 的时间内筛出积性函数 的 的值，使用前提是 能够在 的时间内计算。
对于合数 的分解为 ，记录最小的质因子 的贡献部分为 。作为线性筛的前提，每一个合数都只能被自己的最小质因子筛中。
所以当 被 筛到时，若 是 的倍数，则 ，否则 。若有 ，说明 ，此时 可以使用 的时间计算，否则有 。
线性筛欧拉函数
首先，欧拉函数的计算公式 。
有性质：
- ；
- ，此时可以直接
break; ；
- 。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int pri[MAXN],Tot,phi[MAXN];
bool is[MAXN];
inline void sieve(int n)
{
is[1]=1,phi[1]=1;
for(int i=2;i<=n;++i)
{
if(!is[i]) pri[++Tot]=i,phi[i]=i-1;
for(int j=1;j<=Tot&&i*pri[j]<=n;++j)
{
is[i*pri[j]]=1;
if(i%pri[j]==0)
{
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
phi[i*pri[j]]=phi[i]*(pri[j]-1);
}
}
}
|
线性筛莫比乌斯函数
莫比乌斯函数的计算公式太难写了，就不写了。
首先，初始化 ，然后线性筛，筛出：
- ，并执行
break; ；
- 。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int Mu[MAXN],Pri[MAXN],Tot;
bool Is[MAXN];
inline void sieve(int n)
{
Mu[1]=1,Is[1]=1;
for(int i=2;i<=n;++i)
{
if(!Is[i]) Pri[++Tot]=i,Mu[i]=-1;
for(int j=1;j<=Tot&&i*Pri[j]<=n;++j)
{
Is[i*Pri[j]]=1;
if(i%Pri[j]==0)
{
Mu[i*Pri[j]]=0;
break;
}
Mu[i*Pri[j]]=-Mu[i];
}
}
}
|
线性筛主要还是用于预处理的，作为解一些与质数，最大公约数，或者莫比乌斯反演的题的预处理。
杜教筛
在 的时间复杂度内求出一个积性函数 的前缀和。
定义 ，找两个易于求前缀和的积性函数 满足 ，则有：
对于杜教筛的实现，可以线性筛预处理出 的前 项前缀和，再递归计算 ，用 和 记忆化计算结果。
常用的构造 有 等。
求解
对于数论函数 ，我们的任务就是构造一个 关于 的递推式以在低于线性时间的复杂度内求解 的前缀和。
对于任意一个数论函数 必满足：
从而得到递推式：
模板
莫比乌斯函数前缀和
使用整数分块，直接计算 ，预处理前 项，剩余复杂度为
对于无法直接使用 的较大数值，考虑 std::map 。
欧拉函数前缀和
可以使用杜教筛 的前缀和，也可以使用莫比乌斯反演。这里考虑杜教筛：
有
结束。
实现
AC Code
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
| #include<bits/stdc++.h>
const int MAXN=2e6+10;
typedef long long ll;
ll Test,N,Pri[MAXN],Cur,Mubi[MAXN],S_M[MAXN];
bool Vis[MAXN];
std::map<ll,ll>Mp_M;
ll mobius_S(ll x)
{
if(x<MAXN) return S_M[x];
if(Mp_M[x]) return Mp_M[x];
ll ret=1ll;
for(ll i=2,j;i<=x;i=j+1)
{
j=x/(x/i);
ret-=mobius_S(x/i)*(j-i+1);
}
return Mp_M[x]=ret;
}
ll phi_S(ll x)
{
ll ret=0ll;
for(ll i=1,j;i<=x;i=j+1)
{
j=x/(x/i);
ret+=(mobius_S(j)-mobius_S(i-1))*(x/i)*(x/i);
}
return (ret-1)/2+1;
}
inline void Sieve(int N)
{
Mubi[1]=1;
for(int i=2;i<=N;++i)
{
if(!Vis[i])
Pri[++Cur]=i,Mubi[i]=-1;
for(int j=1;j<=Cur&&i*Pri[j]<=N;++j)
{
Vis[i*Pri[j]]=1;
if(i%Pri[j]==0)
{
Mubi[i*Pri[j]]=0;
break;
}
Mubi[i*Pri[j]]=-Mubi[i];
}
}
for(int i=1;i<=N;++i) S_M[i]=S_M[i-1]+Mubi[i];
}
int main()
{
std::cin>>Test;
Sieve(MAXN-1);
while(Test--)
{
scanf("%lld",&N);
printf("%lld %lld\n",phi_S(N),mobius_S(N));
}
}
|
Min_25 筛
也是一种求积性函数前缀和的筛法，时间复杂度为 ，空间复杂度 。要求质数 处的函数值是一个多项式。该筛法要求 是一个多项式（如果不是，可能会算不出来）。
记 为 的质数个数， 表示第 个质数， 表示 的最小质因子， 是一个积性函数。（这里我们定义除法默认下取整）
筛的实现分为两个部分。
Part 1
考虑求解一个式子：
定义一个二元函数 ，表示为：
这里假设函数 的计算方法和都和 中素数的计算方法一致。例如 等之类的。
这里的 被要求为一个完全积性函数，这是执行筛法的要求。而我们要求的 ，所需要的是 ，而 中只有素数的函数值，所以和原式是相等的。
而 以内的数最小质因子显然不会超过 ，所以也可以写成 。
作为筛法，应当考虑 的递推计算。若有 ，则 ，因为不会存在 的数。
那么，我们可以得出 的转移式：
对于 的探讨：考虑 和 的差别，根据 的定义，不难看出， 比 缺少的部分就是那些以 为最小质因子的合数的函数值。所以减去的那部分就是刚刚提及的那部分。
我们尝试把 的空间复杂度压到 。
的第一维用于存储 这些位置，且其转移只存在于 ，而向下取整的除法可结合，即 ，无论怎么除，都只需要 ，只会用到 个关键位置。
的第二维用于转移 ，而与此同时第一维不断缩小，我们只需要 ，可以直接压掉第二维后滚动数组。
下面是 求 以内的质数个数的代码：
1
2
3
4
5
6
7
8
9
10
11
| int sqN=ceil(sqrt(n));
for(int i=1;i<=Tot;++i) g[i]=w[i]-1;
for(int j=1;j<=Cnt;++j)
for(int i=1;i<=Tot&&Pri[j]*Pri[j]<=w[i];++i)
{
int k=w[i]/Pri[j];
if(k<=sqN) k=id[0][k];
else k=id[1][n/k];
g[i]-=g[k]-j+1;
}
write(g[1]);
|
其中
变量申义
Tot 表示关键点个数；
w[i] 表示从大到小的第 i 个关键点；
g[i] 表示当前的 g(w[i],j)；
id[0/1][k] 分别表示 k 和 n/k 是第几个关键点。
从而完成 的计算。
时间复杂度为 。
Part 2
对于求解 在所有位置的函数值之和 。定义一个二元函数为 ：
则有 。
把 的计算拆成素数部分和合数部分，素数部分显然是 。而对于合数部分，我们需要进一步计算。
枚举最小质因子 以及其次幂 ，不重不漏地计算 的合数。枚举幂次，使得 被提及之后，就不会存在质因子 ，函数值就可以直接与括号外相乘。对于 作为合数，不会被枚举，所以我们需要手动加上。
这样可以免去记忆化，直接递归计算。边界是 。
时间复杂度与 相同，也可以是 。