Just a Blog

前言

有关积性函数的相关性质,请参考莫比乌斯反演

与线性筛关系最大的便是以下性质:

$gcd(a,b)=1$时,满足$f(ab)=f(a)f(b)$

实现方法

首先明确一点,所有的线性筛出积性函数的方法都是通过线性筛素数实现的。

如何筛素数?

朴素筛法(复杂度$O(n^2)$~$O(n\sqrt {n})$)

枚举每一个数和它的因子,如果只有1与它本身是它的因子,那么它就是质数。

因为所有$>\sqrt{n}$的因子都可以被小于$\sqrt{n}$的因子表示,所以可以只枚举到$\sqrt{n}$,但是复杂度还是不够优秀。

埃氏筛(复杂度$O(nloglogn)$)

思想就是从枚举因子转化为枚举倍数。

很明显质数的倍数都不是质数,所以对于每个质数,枚举其倍数,并将其标记成非质数。

很明显这样做的话会使得一些数被筛去好几次,比如6会被2和3筛去,造成了时间上的浪费。

虽然这种筛法在实际应用上有更好的代替,但是其将枚举因子转化为枚举倍数的思想却能够优化解决很多问题。

欧拉筛(复杂度$O(n)$)

为了解决埃氏筛反复筛去一个数多次的问题,我们规定,每一个数只能被其最小的质因子删去。

通过代码进行进一步讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define fr(i, j, k) for(register int i = j; i <= k; ++i)
const int maxn = 40010;
int prime[maxn], tot;
char vis[maxn];
void innt(){
vis[1] = 1;
fr(i, 2, maxn - 1){
if(!vis[i])prime[++tot] = i;
for(int j = 1; j <= tot && i * prime[j] <= maxn; ++j){
vis[i * prime[j]] = 1;
if(i % prime[j] == 0) break;//关键点!!!!!!
}
}
}

代码中有一句:

1
if(i % prime[j] == 0)break;

正是这句话保证了每个数只会被其最小的质因子删去。

线性筛欧拉函数

欧拉函数定义

欧拉函数是指小于x的整数中与x互质的数的个数,用$\varphi$表示,特殊的:$\varphi(1)=1$。

欧拉函数性质

1.对于质数$p$, $\varphi(p)=p-1$

根据定义显然

2.对于质数$p$,

若$p$是$x$的约数,则 $\varphi(xp)=\varphi(x)p$ 。

若p不是x的约数,则 $\varphi(xp)=\varphi(x)\varphi(p)=\varphi(x)*(p-1)$ 。

证明:

1.若$x\%p==0$则$ip$的最小素因子的个数多了1,其余无变化

2.若$x\%p!=0$,因为$\varphi$s是积性函数,所以当$x$与$p$互质时$\varphi(x
p)=\varphi(x)*\varphi(p)$。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define fr(i, j, k) for(register int i = j; i <= k; ++i)
const int maxn = 40010;
int prime[maxn], phi[maxn], tot;
char vis[maxn];
void innt(){
vis[1] = 1, phi[1] = 1;
fr(i, 2, maxn){
if(!vis[i]){prime[++tot] = i;phi[i] = i - 1;}
for(int j = 1; j <= tot && i * prime[j] <= maxn; ++j){
vis[i * prime[j]] = 1;
if(i % prime[j]){
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i*prime[j]] = phi[i] * (prime[j] - 1);
}
}
}

线性筛莫比乌斯函数

莫比乌斯函数定义及性质

请参考莫比乌斯反演

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define fr(i, j, k) for(register int i = j; i <= k; ++i)
const int maxn = 40010;
int prime[maxn], mu[maxn], tot;
char vis[maxn];
void innt(){
mu[1] = 1;
vis[1] = 1;
fr(i, 2, maxn){
if(!vis[i])prime[++cnt] = i, mu[i] = -1;
for(int j = 1, w; j <= cnt && (w = (i * prime[j])) <= maxn; ++j){
vis[w] = 1;
if(!(i % prime[j])){mu[w] = 0;break;}
else mu[w]=-mu[i];
}
}
}

 评论