线性筛筛质数

线性筛为什么可以做到线性，它让每个合数只被最小的质因数筛选一次而不发生重复筛选

1
2
3
4
5
6
7
8
9
10
rep(i,2,n){
    if(!vis[i]) pri[++cnt]=i;
    for(int j=1;j<=cnt and pri[j]*i<=1e8;j++){
        int m=i*pri[j];
        vis[m]=1;
        //说明pri[j]是i的最小质因数，同样是被筛数m的最小质因数，所以再后面的数就应该由pri[j]筛掉，而不是j++
        //那么6*3=18应该等到i=9是被pri[j]=2筛掉，所以i=6时遇到pri[j]=2就可以停止了
        if(i%pri[j]==0) break;
    }
}

线性筛求约数个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void init(){
    a[1]=1,d[1]=1;
    int cnt=0;
    rep(i,2,1e7){
        if(!vis[i]){
            pri[++cnt]=i;
            a[i]=1;d[i]=2;
        }
        for(int j=1;j<=cnt and i*pri[j]<=1e7;j++){
            int m=i*pri[j];
            vis[m]=1;
            if(i%pri[j]==0){
                a[m]=a[i]+1;
                d[m]=d[i]/a[m]*(a[m]+1);
                break;
            }else{
                a[m]=1;
                d[m]=d[i]*2;
            }
        }
    }
}

线性筛求约数和

a[i]是最小质因数的约数和

d[i]是函数值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void init(){
    int cnt=0;
    rep(i,2,1e7){
        if(!vis[i]){
            pri[++cnt]=i;
            a[i]=d[i]=i+1;
        }
        for(int j=1;j<=cnt and i*pri[j]<=1e7;j++){
            int m=i*pri[j];
            vis[m]=1;
            if(i%pri[j]==0){
                a[m]=a[i]*p[j]+1;
                d[m]=d[i]/a[i]*a[m]
                break;
            }else{
                a[m]=p[j]+1;
                d[m]=d[i]*a[m];
            }
        }
    }
}

线性筛求莫比乌斯函数

莫比乌斯函数：

包含相同质因子为0

不同质因数为偶数个为1，奇数为-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void init(){
    int cnt=0;
    rep(i,2,1e7){
        if(!vis[i]){
            pri[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt and i*pri[j]<=1e7;j++){
            int m=i*pri[j];
            vis[m]=1;
            if(i%pri[j]==0){
                mu[m]=0;s
                break;
            }else{
                //比i多了一个质因数，奇偶互换0不变，所以取反
                mu[m]=-mu[i];
            }
        }
    }
}
莫比乌斯反演

设任意算术函数f, 其和函数为 即n的所有正因数的函数和称为和函数

莫比乌斯函数就是和函数到原函数的反向过程

线性筛与积性函数

其实上诉问题，因子和 和约数个数 都是积性函数

积性函数？对于互为质数的正整数p,q有

积性函数都可以用线性筛求解1~n的所有函数值

O(n)求1~n的欧拉函数是一个比较简单但直观的例子，所以线性筛也被称为欧拉筛

欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve(){
    int cnt=0;
    rep(i,2,n){
        if(!vis[i]){
            phi[i]=i-1;
            //单独考虑质数的情况
            pr[++cnt]=i;
        }
        for(int j=1;j<=cnt and pr[j]<=n/i;j++){
            int m=i*pr[j];
            vis[m]=1;
            //需要特别判断pq不互质的情况的
            if(i%pr[j]==0){
                //没有出现新的质因数p，就扩大到m就行
                phi[m]=phi[i]*pr[j];
                break;
            }else{
                //出现了新的质因数
                phi[m]=phi[i]*phi[pr[j]];
            }
        }
    }
}

完全积性函数 华华给月月出题

幂函数对于任何的p,q都满足 被称为完全积性函数，不需要单独考虑遍历值不为最小质因数的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
cin>>n;
f[1]=1;
int cnt=0;
rep(i,2,n){
    if(!vis[i]){
        //单独考虑一下质数就行
        pri[++cnt]=i;
        f[i]=qpow(i,n,p)%p;
    }
    for(int j=1;j<=cnt and pri[j]<=n/i;j++){
        vis[i*pri[j]]=1;
        //通过乘性关系递推
        f[i*pri[j]]=f[i]*f[pri[j]]%p;
        if(i%pri[j]==0) break;
    }
}