数论知识总结-线性筛

NOIP爆零の蒟蒻又来学数论辣

注：下文p都是质数

线性筛素数

也叫欧拉筛？

int pr[maxn];bool flg[maxn];
int main(){
    for(rg int i=2;i<maxn;++i){
        if(!flg[i])pr[++pr[0]]=i;
        for(rg int j=1;i*pr[j]<=n&&j<=pr[0];++j){
            flg[i*pr[j]]=1;
            if(i%pr[j]==0)break;//重点
        }
    }
}

这样筛的话，若合数(n=p_1^{a_1}p_2^{a_2}cdots p_k^{a_k}(p_1<p_2<cdots<p_k))，则(n)会在(i=n/p_1,pr[j]=p_1)处被筛去，也只会在这里被筛去。也就是说，每个数都会被它最小的质因子筛去。if(i%pr[j]==0)break;这句话保证了复杂度。

没了？

线性筛积性函数

积性函数就是定义在(mathbb{Z^+})上的函数，且对于任何一对互质的正整数(x,y)满足(f(x)f(y)=f(xy))，根据定义一定满足(f(1)=1)

然而我只会一丁点，以后再补

筛这个必须深刻理解线性筛的过程

线性筛欧拉函数

有点点麻烦。

首先，(phi(p)=p-1)

然后，将合数(n)分解成(n=px)（p是n最小的质因子），

若(p mid x)则(phi(n)=phi(x) imesfrac{p-1}{p} imesfrac{n}{x}=phi(x) imes(p-1))

否则(phi(n)=phi(x) imesfrac{n}{x}=phi(x) imes p)

int phi[maxn],pr[maxn];bool flg[maxn];
main(){
	phi[1]=1;
    for(rg int i=2;i<maxn;++i){
        if(!flg[i])pr[++pr[0]]=i,phi[i]=i-1;
        for(rg int j=1;i*pr[j]<maxn&&j<=pr[0];++j){
            flg[i*pr[j]]=1;
            if(i%pr[j]==0){phi[i*pr[j]]=phi[i]*pr[j];break;}
            phi[i*pr[j]]=phi[i]*(pr[j]-1);
        }
    }
}

线性筛莫比乌斯函数

这个很好办。

首先，(mu(p)=-1)

然后，将合数(n)分解成(n=px)（p是n最小的质因子），

若(p mid x)则(mu(n)=-mu(x))

否则(mu(n)=0)

int mu[maxn],pr[maxn];bool flg[maxn];
main(){
    mu[1]=1;
    for(rg int i=2;i<maxn;++i){
        if(!flg[i])pr[++pr[0]]=i,mu[i]=-1;
        for(rg int j=1;i*pr[j]<maxn&&j<=pr[0];++j){
            flg[i*pr[j]]=1;
            if(i%pr[j]==0){mu[i*pr[j]]=0;break;}
            mu[i*pr[j]]=-mu[i];
        }
    }

线性筛前N个数的约数个数

极其麻烦。

这个好像叫(d)函数

看(d=(a_1+1)(a_2+1)cdots(a_k+1))

然而还不行，你还要记这个数的(a_1)（定义在上面）记为(f)

首先，(d(p)=2,f(p)=1)

然后，将合数(n)分解成(n=px)（p是n最小的质因子），

若(p mid x)则(d(n)=2d(x),f(n)=1)（d乘2相当于是要不要新选p）

否则(f(n)=f(x)+1,d(n)=d(x)*frac{f(n)+1}{f(x)+1})

（我好像把这个套路粘了两遍）

int pr[maxn],d[maxn],f[maxn];bool flg[maxn];
int main(){
    int n=gi();
    for(rg int i=1;i<=n;++i)d[i]=1;
    for(rg int i=2;i<=n;++i){
        if(!flg[i])pr[++pr[0]]=i,d[i]=2,f[i]=1;
        for(rg int j=1;i*pr[j]<=n&&j<=pr[0];++j){
            flg[i*pr[j]]=1;
            if(i%pr[j]==0){
                f[i*pr[j]]=f[i]+1;
                d[i*pr[j]]=d[i]/(f[i]+1)*f[i*pr[j]];
                break;
            }
            f[i*pr[j]]=1;
            d[i*pr[j]]=d[i]*2;
        }
    }
}