东灯的寒舍

你特别好，我喜欢你

0%

线筛及其应用

Posted on Edited on In

线性筛是数论中主要的算法，在求素数、配合算数基本定理求积性函数中有重要作用。

本文研究线性筛和和线性筛的具体应用。

Native

在对埃筛原理有所了解的前提下，我们来介绍线性筛的原理。

与埃筛不同的是，线筛的筛素数策略是：让每个合数只由自己的最小质因数筛出，而不被更大的质因数筛出，以保证复杂度。

先来看代码：

1
2
3
4
5
6
7
8
9
10
11
bitset<100000010>isPrime;
int Prime[6000010],cnt;
void GetPrime(int N){
	for(int i=2;i<=N;++i){
		if(!isPrime[i])Prime[++cnt]=i;
		for(int j=1;j<=cnt&&i*Prime[j]<=N;++j){
			isPrime[i*Prime[j]]=1;
			if(i%Prime[j]==0)break;
		}
	}
}

可以注意到该代码中第 8 行位置，当 $i \ mod \ Prime[j] = 0$ 时候跳出 $i$ 的循环，这里做出解释：$Prime[j]$ 一定是 $i$ 的最小质因子，否则将会出现在 $j$ 之前，如果继续向下枚举素数构造合数，构造出的合数中一定有一个因数是 $Prime[j]$ 不满足每个合数由自己的最小质因子筛出，所以在这种情况下跳出循环。

正确性证明

假设一个合数 $N$ 的最小质因数是 $p$，则一定存在 $M=\frac{N}{p}$，可以注意到 $M$ 的最小质因子一定大于等于 $p$。

又发现在循环中 $M$ 一定比 $N$ 先出现($M<N$)，且 $M$ 循环时保证可以筛掉到 $M$ 的最小质因数，这里设为 $q$，结合刚才的结论可以得知 $p \leq q$，因此 $Mp$ 即 $N$ 一定可以被筛掉。

对 $N$ 推广到所有合数，线性筛的正确性就得到了证明。

线性复杂度证明

注意到埃筛中造成复杂度较大的地方是每个合数都会被重复筛除，即 $ i_2 \cdot p_1 $ 还会被 $i_2 \cdot p_2$ 重复筛出(此时 $p_1 $与 $p_2$ 是该数的两个不同质因数)。

假设合数 $N$ 已经被 $p_1$ 筛除，再假设 $N$ 有一个另外的质因数 $p_2$， 如果 $N$ 被 $p_2$ 筛出那么一定是在 $i=\frac{N}{p_2}$ 时，但是又考虑到 $p_1|\frac{N}{p_2}$，循环在枚举到 $p_1$ 时就 会跳出，能够保证线性的复杂度。

应用

利用线性筛可以基于算数基本定理在线性复杂度内求出积性函数的值。

莫比乌斯函数

莫比乌斯函数定义为

考虑在线筛构造出一个合数时，通过 $i \ mod \ Prime[j]==0$的条件判断是否存在 $Prime[j]^2 \ | \ i \cdot Prime[j]$，如果是，则该合数的情况为上述描述中的第一种，否则 $Prime[j]$ 对于 $i \cdot Prime[j]$ 来说就是一个单次的质因子，从 $i$ 的莫比乌斯函数转移只需要 $ \mu ( i \cdot Prime[j] ) = - \mu (i)$。

特别的，质数的莫比乌斯函数值一定为 $-1$。

接下来可以采用线筛求得：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int mu[MAXN];
bitset<MAXN>vis;
vis[1]=mu[1]=1;
for(int i=2;i<=N;++i){
    if(!vis[i]){
        Prime[++cnt]=i;
        mu[i]=-1;
    }
    for(int j=1;j<=cnt&&i*Prime[j]<=N;++j){
        vis[i*Prime[j]]=1;
        if(!(i%Prime[j])){
            mu[i*Prime[j]]=0;
            break;
        }
        mu[i*Prime[j]]=-mu[i];
    }
}

欧拉函数

需要以下三个与欧拉函数有关的性质：

对于任意质数 $p$ 和大于 $p$ 的合数 $i$。

  • $\phi(p)=p-1$。

  • 如果 $i \ mod \ p \not=0$，则 $(i,p)=1$，因此 $\phi(i \cdot p)=\phi(i) \cdot \phi(p)=\phi(i) \cdot (p-1)$。

  • 如果 $i \ mod \ p =0$，则 $\phi(i \cdot p)=\phi(i) \cdot p$。

关于第三个结论的证明可以参考此博客。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
long long phi[MAXN],prime[MAXN],tot;
bitset<MAXN>check;
inline void euler(long long N){
    phi[1]=1;
    for(long long i=2;i<=N;++i){
        if(!check[i]){
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(long long j=0;j<tot;++j){
            if(i*prime[j]>N)break;
            check[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

约数个数

根据算数基本定理中提供的约数个数定理，我们可以用线筛用线性复杂度求出约数个数。

这里用 $a[i]$ 表示当前数字的最小质因子的次数，接下来分两种情况：

  • $i \ mod \ Prime[j]=0$ 时，可以发现只有这种情况下构造出的 $i \times Prime[j]$ 中 $Prime[j]$ 的次数会增加，因此在这里处理次数增加的情况。很多人总是被一个观念误导： 这个数没有被筛出多次，我是如何叠次数的？实际上这个质因数次数是被一个已经有多次的合数和该质数构造出来的，比如 $8$ 是被 $2 \times 4$ 构造出来的。

  • $i \ mod \ Prime[j]\not=0$ 时，即 $i \times Prime[j]$ 中 $Prime[j]$ 的次数只有一次，又因为每个合数一定会被最小质因数筛出，因此我们也求出了 $a[i \times Prime[j]]=1$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int prime[MAXN],D[MAXN],a[MAXN],tot;
bitset<MAXN>vis;
void GetD(int N){
    vis[1]=D[1]=a[1]=1;
    for(int i= 2;i<=N;++i){
        if(!vis[i])prime[++tot]=i,D[i]=2,a[i]=1;
        for(int j=1;j<=tot&&i*prime[j]<=N;++j){
            vis[i*prime[j]]=1;
            if(!(i%prime[j])){
                D[i*prime[j]]=D[i]/(a[i]+1)*(a[i]+2);
                a[i*prime[j]]=a[i]+1;
                break;
            }
            D[i*prime[j]]=D[i]*D[prime[j]];
            a[i*prime[j]]=1;
        }
    }
}