线性筛

· · 个人记录

线性筛是数论中非常重要的一部分，常常被用作降低预处理的复杂度，通常降低至 O(n)\ \ (要不然为啥叫“线性”)。

本篇 blog 介绍各种线性筛。

除了线性筛质数，其他线性筛都要求：所求的函数必须为积性函数。

所谓积性函数，即：对于任意互质的正整数 a 和 b，有 f(ab)=f(a)\times f(b) 的数论函数。

若是没有互质的限制，则称函数为完全积性函数。

线性筛质数(欧拉筛)：

#define Maxn 10000007
int prime[Maxn];
bool vis[Maxn]; // 若 vis[i] = true，则表示 i 不是质数。
int get_prime()
{
    static int cnt=0;
    long long k=0ll;
    vis[0]=vis[1]=true;
    for(long long i=2ll;i<Maxn;++i) {
        if(!vis[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt && (k=i*prime[j])<Maxn;++j) {
            vis[k]=true;
            if(i%prime[j]==0) break;
        }
    }
    return cnt; // 返回质数个数。
}

关键在于 if-break 语句，这句话能保证每个合数均被其最小的质因子筛掉。

（挖坑待填）。

线性筛求ID函数：

```cpp #define Maxn 10000007 int ID[Manx], prime[Maxn]; int get_ID() { static int cnt=0; long long k=0ll; ID[1]=1; for(long long i=2ll;i<Maxn;++i) { if(!ID[i]) ID[i]=i, prime[++cnt]=i; for(int j=1;j<=cnt && (k=i*prime[j])<Maxn;++j) { ID[k]=k; if(i%prime[j]==0) break; } } } ``` *** # 线性筛欧拉函数： 欧拉函数是积性函数。 ```cpp #define Maxn 10000007 int phi[Maxn], prime[Maxn]; int get_phi() { static int cnt=0; long long k=0ll; for(long long i=2ll;i<Maxn;++i) { if(!phi[i]) phi[i]=i-1, prime[++cnt]=i; for(int j=1;j<=cnt && (k=i*prime[j])<Maxn;++j) { if(i%prime[j]==0) {phi[k]=phi[i]*prime[j]; break;} phi[k]=phi[i]*(prime[j]-1); } } return cnt; } ``` *** # 线性筛求莫比乌斯函数： 莫比乌斯函数是积性函数。 ```cpp #define Maxn 10000007 int mu[Maxn], prime[Maxn]; bool vis[Maxn]; int get_mu() { static int cnt=0; long long k=0ll; mu[1]=1; for(long long i=2ll;i<Maxn;++i) { if(!vis[i]) {mu[i]=-1; prime[++cnt]=i;} for(int j=1;j<=cnt && (k=i*prime[j])<Maxn; ++j) { vis[k]=true; if(i%prime[j]==0) {mu[k]=0; break;} mu[k]=-mu[i]; } } return cnt; } ``` *** # 线性筛求约数个数： 记 $Div[i]$ 表示 $i$ 的约数个数 （约数的英文：$Divisor$）。 约数个数显然是个积性函数。 ```cpp #define Maxn 10000007 int min_prim[Maxn], Div[Maxn], prime[Maxn]; int get_Div() { static int cnt=0; long long k=0ll; Div[1]=1; for(long long i=2ll;i<Maxn;++i) { if(!Div[i]) Div[i]=2, prime[++cnt]=i, min_prim[i]=1; for(int j=1;j<=cnt && (k=i*prime[j])<Maxn;++j) { if(i%prime[j]==0) {min_prim[k]=min_prim[i]+1; Div[k]=Div[i]/(min_prim[i]+1)*(min_prim[k]+1); break;} Div[k]=Div[i]<<1; } } return cnt; } ``` *** # 线性筛求约数和： 这个就恶心了，但其实和求约数个数的差不多。 $i$ 的约数和记做 $\sigma(i)$ 。 ```cpp #define Maxn 10000007 int sigma[Maxn], Smin_prim[Maxn], prime[Maxn]; int get_sigma() { static int cnt=0; long long k=0ll; sigma[1]=1; for(long long i=2ll;i<Maxn;++i) { if(!sigma[i]) sigma[i]=i+1, Smin_prim[i]=i+1, prime[++cnt]=i; for(int j=1;j<=cnt && (k=i*prime[j])<Maxn;++j) { if(i%prime[j]==0) {Smin_prim[k]=Smin_prim[i]*prime[j]+1; sigma[k]=sigma[i]/Smin_prim[i]*Smin_prim[k]; break;} Smin_prim[k]=prime[j]+1; sigma[k]=sigma[i]*sigma[prime[j]]; } } return cnt; } ``` *** # 小合集： ```cpp // 线性筛小合集。 #define Maxn 10000007 int prime[Maxn]; bool vis[Maxn]; // 若 vis[i] = true，则表示 i 不是质数。 int get_prime() { static int cnt=0; long long k=0ll; vis[0]=vis[1]=true; for(long long i=2ll;i<Maxn;++i) { if(!vis[i]) prime[++cnt]=i; for(int j=1;j<=cnt && (k=i*prime[j])<Maxn;++j) { vis[k]=true; if(i%prime[j]==0) break; } } return cnt; // 返回质数个数。 } int ID[Manx], prime[Maxn]; int get_ID() { static int cnt=0; long long k=0ll; ID[1]=1; for(long long i=2ll;i<Maxn;++i) { if(!ID[i]) ID[i]=i, prime[++cnt]=i; for(int j=1;j<=cnt && (k=i*prime[j])<Maxn;++j) { ID[k]=k; if(i%prime[j]==0) break; } } } int phi[Maxn], prime[Maxn]; int get_phi() { static int cnt=0; long long k=0ll; for(long long i=2ll;i<Maxn;++i) { if(!phi[i]) phi[i]=i-1, prime[++cnt]=i; for(int j=1;j<=cnt && (k=i*prime[j])<Maxn;++j) { if(i%prime[j]==0) {phi[k]=phi[i]*prime[j]; break;} phi[k]=phi[i]*(prime[j]-1); } } return cnt; } int mu[Maxn], prime[Maxn]; bool vis[Maxn]; int get_mu() { static int cnt=0; long long k=0ll; mu[1]=1; for(long long i=2ll;i<Maxn;++i) { if(!vis[i]) {mu[i]=-1; prime[++cnt]=i;} for(int j=1;j<=cnt && (k=i*prime[j])<Maxn; ++j) { vis[k]=true; if(i%prime[j]==0) {mu[k]=0; break;} mu[k]=-mu[i]; } } return cnt; } int min_prim[Maxn], Div[Maxn], prime[Maxn]; int get_Div() { static int cnt=0; long long k=0ll; Div[1]=1; for(long long i=2ll;i<Maxn;++i) { if(!Div[i]) Div[i]=2, prime[++cnt]=i, min_prim[i]=1; for(int j=1;j<=cnt && (k=i*prime[j])<Maxn;++j) { if(i%prime[j]==0) {min_prim[k]=min_prim[i]+1; Div[k]=Div[i]/(min_prim[i]+1)*(min_prim[k]+1); break;} Div[k]=Div[i]<<1; } } return cnt; } int sigma[Maxn], Smin_prim[Maxn], prime[Maxn]; int get_sigma() { static int cnt=0; long long k=0ll; sigma[1]=1; for(long long i=2ll;i<Maxn;++i) { if(!sigma[i]) sigma[i]=i+1, Smin_prim[i]=i+1, prime[++cnt]=i; for(int j=1;j<=cnt && (k=i*prime[j])<Maxn;++j) { if(i%prime[j]==0) {Smin_prim[k]=Smin_prim[i]*prime[j]+1; sigma[k]=sigma[i]/Smin_prim[i]*Smin_prim[k]; break;} Smin_prim[k]=prime[j]+1; sigma[k]=sigma[i]*sigma[prime[j]]; } } return cnt; } ```