“临近深渊的时刻，钟表将停止转动。”
这里定义，本文中提及的 $p$ 在无特殊说明的前提下皆表示质数。
线性筛质数
这个应该很简单啦，使用线性筛即可。背板子。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| bool is[MAXN],pr[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;
}
}
}
|
有意思的练习题
这道题有够水的，甚至于 $\mathcal O(n\sqrt n)$ 都能勉强卡过。
不过我们还是先一遍线性筛，然后二分查找第一个比 $n$ 大的质数。
时间复杂度 $\mathcal O(n\log\frac{sum}{\ln sum}+sum)$ ，其中 $sum=2\times 10^6$ 。
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
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
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
const int MAXN=2e6+1;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
int Pri[MAXN],Tot;
bool Is[MAXN];
inline void Sieve()
{
memset(Is,1,sizeof(Is));Is[1]=0;
for(int i=2;i<MAXN;++i)
{
if(Is[i]) Pri[++Tot]=i;
for(int j=1;j<=Tot&&i*Pri[j]<MAXN;++j)
{
Is[i*Pri[j]]=0;
if(i%Pri[j]==0) break;
}
}
}
int N;
int main()
{
Sieve();
read(N);
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);
}
return 0;
}
|
这道题教会我一个道理，最优的筛法并不一定最优。
这道题，如果使用欧拉筛的话，每一个数只会被自己最小的质因子筛掉。而我们的 $p$ 可以是任一质因子。而正巧，我们有一个复杂度没那么优秀，但依然优秀的筛法——埃氏筛。
埃氏筛保证每一个数都会被自己的所有质因子筛到。所以我们直接求取 $1\sim b$ 的所有质数，并在其中处理满足 $(i,j)\ge p$ 条件的，并把它们在并查集中合并。
令当前质数为 $p_0\ge p$ ，我们枚举 $2p_0\sim\min(kp_0,b)$ ，显然，$kp_0$ 和 $(k-1)p_0$ 有一个质因子为 $p_0\ge p$ ，所以 $kp_0$ 和 $(k-1)p_0$ 必在一个集合。所以我们扫一遍，然后把上述的两个连在一起就好了。
时间复杂度如果我没记错的话，是 $\mathcal O(b\log\log b)$ 。
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
const int MAXN=1e5+1;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
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;
}
|
线性筛/欧拉筛
在 $\mathcal O(n)$ 的时间内筛出积性函数 $f$ 的 $1\sim n$ 的值，使用前提是 $f(p^k)$ 能够在 $\mathcal O(1)$ 的时间内计算。
对于合数 $n$ 的分解为 $n=\prod p_i^{k_i}$ ，记录最小的质因子 $p_1$ 的贡献部分为 $g(n)=p_1^{k_1}$ 。作为线性筛的前提，每一个合数都只能被自己的最小质因子筛中。
所以当 $n$ 被 $x\cdot p$ 筛到时，若 $x$ 是 $p$ 的倍数，则 $g(n)=g(x)\times p$ ，否则 $g(n)=p$ 。若有 $g(n)=n$ ，说明 $n=p_1^{k_1}$ ，此时 $f(n)$ 可以使用 $\mathcal O(1)$ 的时间计算，否则有 $f(n)=f(g(n))\times f(\frac{n}{g(n)})$ 。
线性筛欧拉函数
首先，欧拉函数的计算公式 $\varphi(n)=n\times\prod(1-\frac{1}{p_i})$ 。
有性质：
- $\varphi(p)=p-1$ ；
- $\varphi(x\times p)=\varphi(x)\times p,p\mid x$ ，此时可以直接
break; ；
- $\varphi(x\times p)=\varphi(x)\times(p-1),p\not\mid x$ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| bool is[MAXN],pr[MAXN],phi[MAXN],tot;
inline void sieve(int n)
{
memset(is,1,sizeof(is));
is[1]=0,phi[1]=1;
for(int i=2;i<=n;++i)
{
if(is[i]) pr[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot&&i*pri[j]<=n;++j)
{
is[i*pri[j]]=0;
if(i%pri[j]==0)
{
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
phi[i*pri[j]]=phi[i]*(pri[j]-1);
}
}
}
|
线性筛莫比乌斯函数
莫比乌斯函数的计算公式太难写了，就不写了。
首先，初始化 $\mu(1)=1$ ，然后线性筛，筛出：
- $\mu(i\times pri[j])=0,i\% pri[j]=0$ ，并执行
break; ；
- $\mu(i\times pri[j])=-1\times\mu(i),i\% pri[j]\ne 0$ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| bool is[MAXN],pr[MAXN],mu[MAXN],tot;
inline void sieve(int n)
{
memset(is,1,sizeof(is));
is[1]=0;mu[1]=1;
for(int i=2;i<=n;++i)
{
if(is[i]) pr[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot&&i*pri[j]<=n;++j)
{
is[i*pri[j]]=0;
if(i%pri[j]==0)
{
mu[i*pri[j]]=0;
break;
}
mu[i*pri[j]]=-mu[i];
}
}
}
|
线性筛主要还是用于预处理的，作为解一些与质数，最大公约数，或者莫比乌斯反演的题的预处理。
杜教筛
在 $\mathcal O(n^{\frac{2}{3}})$ 的时间复杂度内求出一个积性函数 $f$ 的前缀和。
定义 $S(n)=\sum_{i<n}f(i)$ ，找两个易于求前缀和的积性函数 $g,h$ 满足 $f\ast g=h$ ，则有：
$\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{d\mid i}f(d)g(\frac{i}{d})$
$\sum_{i=1}^nh(i)=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)$
$\sum_{i=1}^nh(i)=g(1)\cdot S(n)+\sum_{d=2}^ng(d)S(\lfloor\frac{n}{d}\rfloor)$
$g(1)\times S(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(d)S(\lfloor\frac{n}{d}\rfloor)$
对于杜教筛的实现，可以线性筛预处理出 $f$ 的前 $\mathcal O(\sqrt n)$ 项前缀和，再递归计算 $S(n)$ ，用 $\operatorname{Hash}$ 和 $\operatorname{map}$ 记忆化计算结果。
常用的构造 $f\ast g=h$ 有 $\mu\ast I=\epsilon,\varphi\ast I=id,id\ast \mu=\varphi$ 等。
求解
对于数论函数 $f$ ，我们的任务就是构造一个 $S(n)$ 关于 $S(\lfloor\frac{n}{i}\rfloor)$ 的递推式以在低于线性时间的复杂度内求解 $f$ 的前缀和。
对于任意一个数论函数 $g$ 必满足：
从而得到递推式：
$\displaystyle g(1)S(n)=\sum_{i=1}^n(f\ast g)(i)-\sum_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$
模板
莫比乌斯函数前缀和
$\displaystyle S_{\mu}(n)=\sum_{i=1}^n\epsilon(i)-\sum_{i=2}^nS_{\mu}(\lfloor\frac{n}{i}\rfloor)=1-\sum_{i=2}^nS_{\mu}(\lfloor\frac{n}{i}\rfloor)$
使用整数分块，直接计算 $\mathcal O(n^{\frac{3}{4}})$ ，预处理前 $n^{\frac{2}{3}}$ 项，剩余复杂度为 $\displaystyle\mathcal O(\int^{n^{\frac{1}{3}}}_{0}\sqrt{\frac{n}{x}}dx)=\mathcal O(n^{\frac{2}{3}})$
对于无法直接使用 $\text{Hash}$ 的较大数值，考虑 std::map 。
欧拉函数前缀和
可以使用杜教筛 $\varphi(n)$ 的前缀和，也可以使用莫比乌斯反演。这里考虑杜教筛：
有 $\varphi\ast 1=id$
结束。
实现
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 筛
也是一种求积性函数前缀和的筛法，时间复杂度为 $\mathcal O(\frac{n^{\frac{3}{4}}}{\log_2n})$ ，空间复杂度 $\mathcal O(\sqrt n)$ 。要求质数 $p$ 处的函数值是一个多项式。该筛法要求 $F(p^k)$ 是一个多项式（如果不是，可能会算不出来）。
记 $cnt$ 为 $\le n$ 的质数个数，$p_i$ 表示第 $i$ 个质数，$R(x)$ 表示 $x$ 的最小质因子，$F(x)$ 是一个积性函数。（这里我们定义除法默认下取整）
$\text{Min}_\text{25}$ 筛的实现分为两个部分。
Part 1
考虑求解一个式子：
定义一个二元函数 $g$ ，表示为：
这里假设函数 $f$ 的计算方法和都和 $F$ 中素数的计算方法一致。例如 $F(x)=\varphi(x),f(x)=x-1$ 等之类的。
这里的 $f$ 被要求为一个完全积性函数，这是执行筛法的要求。而我们要求的 $\sum_{i=1}^{cnt}F(p_i)=g(n,cnt)$ ，所需要的是 $g(n,cnt)$ ，而 $g$ 中只有素数的函数值，所以和原式是相等的。
而 $n$ 以内的数最小质因子显然不会超过 $\sqrt{n}$ ，所以也可以写成 $g(n,m),p^2_m\ge n$ 。
作为筛法，应当考虑 $g(n,j)$ 的递推计算。若有 $p_j^2\ge n$ ，则 $g(n,j)=g(n,j-1)$ ，因为不会存在 $R(i)\ge p_j$ 的数。
那么，我们可以得出 $g(n,j)$ 的转移式：
对于 $otherwise$ 的探讨：考虑 $g(n,j-1)$ 和 $g(n,j)$ 的差别，根据 $g$ 的定义，不难看出，$g(n,j)$ 比 $g(n,j-1)$ 缺少的部分就是那些以 $p_j$ 为最小质因子的合数的函数值。所以减去的那部分就是刚刚提及的那部分。
我们尝试把 $g$ 的空间复杂度压到 $\mathcal O(\sqrt n)$ 。
$g$ 的第一维用于存储 $\frac{n}{i}$ 这些位置，且其转移只存在于 $n\to \frac{n}{p_j}$ ，而向下取整的除法可结合，即 $\frac{\frac{x}{a}}{b}=\frac{x}{ab}$ ，无论怎么除，都只需要 $g(n,m)$ ，只会用到 $\mathcal O(\sqrt n)$ 个关键位置。
$g$ 的第二维用于转移 $j\to j-1$ ，而与此同时第一维不断缩小，我们只需要 $g(n,m)$ ，可以直接压掉第二维后滚动数组。
下面是 $F(x)=1,g(n,m)$ 求 $n$ 以内的质数个数的代码：
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]);
|
其中
1
2
3
4
| Tot表示关键点个数
w[i]表示从大到小的第i个关键点
g[i]表示当前的g(w[i],j)
id[0/1][k]分别表示k和n/k是第几个关键点
|
从而完成 $\sum\limits_{x=1}^{n}F(x)[x\in Prime]$ 的计算。
时间复杂度为 $\mathcal O(\frac{n^{\frac{3}{4}}}{\log_2n})$ 。
Part 2
对于求解 $F(x)$ 在所有位置的函数值之和 $ans=\sum\limits_{i=1}^{n}F(i)$ 。定义一个二元函数为 $S$ ：
则有 $ans=S(n,1)+F(1)$ 。
把 $S$ 的计算拆成素数部分和合数部分，素数部分显然是 $g(n,cnt)-\sum\limits_{i=1}^{j-1}F(p_i)$ 。而对于合数部分，我们需要进一步计算。
枚举最小质因子 $p_k$ 以及其次幂 $e$ ，不重不漏地计算 $R(i)\ge p_j$ 的合数。枚举幂次，使得 $p_k^e$ 被提及之后，就不会存在质因子 $p_k$ ，函数值就可以直接与括号外相乘。对于 $p_k^e,e\ge 2$ 作为合数，不会被枚举，所以我们需要手动加上。
这样可以免去记忆化，直接递归计算。边界是 $n=1,\vee p_j>n,S(n,j)=0$ 。
时间复杂度与 $\text{Part 1}$ 相同，也可以是 $\mathcal O(n^{1-\epsilon})$ 。