线性筛 欧拉筛
线性筛（又称欧拉筛）是一种线性求素数的筛法，可以在 \(O(n)\) 的时间内找出 \(n\) 以内的所有素数。
线性筛的基本思想是，对于 \(i\) 从
\(2\) 到 \(n\)
的每个数，如果它不是素数，则枚举已筛出的每个素数，若其非 \(i\) 的因子，则将 \(i\)
乘上该素数的积标记为已被筛掉。直到枚举到 \(i\) 的最小质因子。这样，当 \(i\) 到 \(n\)
遍历完成时，所有没有被标记的数都是素数。并且每个数都被枚举到一遍。
线性筛的实现可以用一个数组 mark
标记是否被筛掉，用一个数组 prime 保存素数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int prime[maxl];
bool mark[maxl];
int tot;
inline void oula()
{
for(int i=2;i<=maxl;i++)
{
if(!mark[i])prime[++tot]=i;
for(int j=1;j<=tot and i+prime[j]<=maxl;j++){
mark[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
|
应用
根据欧拉筛的特点，每个合数只会被枚举到一次，被枚举到的时候已知其最小质因子。因此，我们可以同时求出积性函数的值。
积性函数：\(f(n)\) 满足 \(f(1)=1\) 且 \(\forall x,y\in \mathbb{N}^*,\gcd(x,y)=1\Rightarrow
f(xy)=f(x)f(y)\)
完全积性函数：\(f(n)\) 满足 \(f(1)=1\) 且 \(\forall x,y\in \mathbb{N}^*,\Rightarrow
f(xy)=f(x)f(y)\)
欧拉函数
欧拉函数 \(\varphi (x)\) 是 \(x\) 以内与 \(x\) 互素的数的个数。为积性函数。
若要求单个数的phi值：
BZOJ2705
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
| #include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
ll n,ans;
int m;
ll phi(ll x)
{
ll t=x;
for(ll i=2;i<=m;i++)
if(x%i==0)
{
t=t/i*(i-1);
while(x%i==0)x/=i;
}
if(x>1)t=t/x*(x-1);
return t;
}
int main()
{
scanf("%lld",&n);
m=sqrt(n);
for(int i=1;i<=m;i++)
if(n%i==0)
{
ans+=(ll)i*phi(n/i);
if(i*i<n)ans+=(ll)(n/i)*phi(i);
}
printf("%lld",ans);
return 0;
}
|
如要算出范围内所有的phi值：
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e8;
inline int read()
{
int x=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
int phi[maxn],prime[maxn>>1],tot,n,ans;
bool mark[maxn];
inline void oula()
{
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!mark[i])
{
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot and i*prime[j]<=n;j++)
{
mark[i*prime[j]]=1;
if(i%prime[j]==0)phi[i*prime[j]]=phi[i]*prime[j];
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
if(i%prime[j])break;
}
}
}
int main()
{
n=read()；
int m=read();
oula();
while(m--)printf("%d\n",prime[read()]);
return 0;
}
|
mobius函数
莫比乌斯函数 \(\mu(x)\)：
\[
\mu(x)=\begin{cases}
0,&\frac x{p_1}\mod p_1 = 0\\
-\mu(\frac x{p_1}) , & \text{otherwise}
\end{cases}
\]
其中 \(p_1\) 是 \(x\) 的最小质因子。
可以看出，若 \(x\)
有多个相同质因子，则 \(\mu(x)=0\)。否则
\(\mu(x)=(-1)^r\)，其中 \(r\) 是 \(x\) 的质因子个数。
约数个数和
根据算术基本定理，设数 \(n\)
的约数个数和为 \(d_n\)，有： \[
n=\prod_{p_i\mid n, p_i\mathrm{\ is\ a\ prime}}p_i^{g_i}\\
d_n=\prod g_i+1
\] 要筛 \(d\) 我们还需要一个
\(g\)
来表示该数的最小素因子的数量，以便进行第二条转移。
- \(g_i=1,d_i=2\)。
- 此时枚举数 \(i\)
的最小约数已经之前被更新过了并且一定是当前正在枚举的 \(p\) ，则 \(g_{tmp}=g_i+1\)。对于 \(d_{tmp}\)，根据上述公式，那我们就从 \(d_i\)
进行转移，更新最小约数的贡献，即除掉更改的贡献乘上正确的，即 \(d_{tmp}=d_i*\frac{g_{tmp}+1}{g_i+1}\)。
- 此时枚举的 \(p\)
是最小的素因子，那么根据公式，\(g_{tmp}=1,d_{tmp}=d_i*2\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| d[1]=1;
for(int i=2;i<=n;i++){
if(!mark[i]) p[++tot]=i,d[i]=2,g[i]=1;
for(int j=1,tmp;j<=tot and (tmp=i*p[j])<=n;j++){
mark[tmp]=true;
if(i%p[j]==0){
g[tmp]=g[i]+1;
d[tmp]=d[i]/(g[i]+1)*(g[tmp]+1);
break;
}
g[tmp]=1;
d[tmp]=d[i]*[g[tmp]+1];
}
}
|
约数和
根据算术基本定理，已知 \(\sigma\)
为约数和，有： \[
\sigma_n=\prod_{p_i\mid n, p_i\mathrm{\ is\ a\
prime}}\sum_{j=0}^{a_i}p_i^j
\]
注意这里的 \(a\) 与上文的 \(g\)
表示意义相同，为每个素数的个数。我们定义 \(g\) 为最小的 \(p\) 的 \(\sum_{j=0}p^j\)。
- \(g_i=\sigma_i=i+1\)
- 根据 \(g\) 的定义，我们要更新 \(g\) 就相当于给原来的 \(g\) 乘上 \(p\) 并加 1。对于 \(\sigma\)，和上面的转移类似，我们从 \(i\) 转移即可。\(\sigma_{tmp}=\sigma_i*\frac{g_{tmp}}{g_i}\)。
- 此时我们计算上一个新的质数的贡献即可，和上面类似。
代码中 \(\sigma\) 用 \(f\) 代替。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| f[1]=1;
for(int i=2;i<=n;i++){
if(!mark[i]) p[++tot]=i,g[i]=f[i]=i+1;
for(int j=1,tmp;j<=tot and (tmp=i*p[j])<=n;j++){
mark[tmp]=true;
if(i%p[j]==0){
g[tmp]=g[i]*p[j]+1;
f[tmp]=f[i]/g[i]*g[tmp];
break;
}
g[tmp]=p[j]+1;
f[tmp]=f[i]*f[p[j]];
}
}
|
