欧拉筛

1.筛质数

先看看线性筛本体，它的功能是判断质数，以及求最小质因数

1.记录minfactor,prime

2.对cur一直用prime数组筛去剩下的合数

这里判断质数的标准很简单，就是判断一个数的最小质因数是否就是它本身

由于是求最小质因数，$prime[j]<=minfact[i]$,这样可以证明每个合数仅被它的最小质因数筛到，保证线性复杂度

2.求$\phi(n)$

$\phi(p)=p-1$,利用这个性质，可在判断质数的同时筛出它的欧拉函数

由欧拉函数的积性性得,$\phi(mn)=\phi(m)\phi(n)$

当$minfact[i]=prime[j]$,即有重复质因子时，$\phi(p^k)=p^{k-1}(p-1)$,乘上p即可

不然乘上(p-1)

3.求$\mu(n)$

$\mu(p)=-1$,利用这个性质，可在判断质数的同时筛出它的莫比乌斯函数

当$minfact[i]=prime[j]$,即有重复质因子时，$\mu(n)=0$

不然乘上$\mu(n)=-\mu(i)$

4.求$d(n)$

比前面的两个函数要麻烦一些，求$d(n)$要记录n中最小质因子数$cnt[n]$

对于质数,$cnt[n]$很显然等于1

接着考虑$d(n)$,$n=\Pi^k_{i=1}p_i^{a_i}$,$d(n)=\Pi^k_{i=1}(p_i+1)$

如果$minfact[i]=prime[j]$,由牛顿二项式定理得，$d(n)=d(i)/(cnt[i]+1)*(cnt(i)+2)$

不然$d(n)=d(i)*d(prime[j])$

5.求$\sigma(n)$

类似于求$d(n)$,不过这次要记录一个数组$sum[i]=\Sigma_{i=0}^kp^i$,p表示n的最小质因数，$sum[i]$表示最小质因数的k次幂下的和

对于质数，$sum[i]$很显然等于p+1

接着考虑$\sigma(n)$,$\sigma(n)=\Pi_{i=1}^k\Sigma_{j=0}^{a_i}p^j_i$

如果$minfact[i]=prime[j]$,在求和式中加入一项$p^{k+1}$,等同于乘$(sum[i]*p+1)/sum[i]$

不然$\sigma(n)=\sigma(i)*\sigma(prime[j])$

//mf 最小质因数
//pr 质数 
void sieve(){
    For(i,2,LIM){
        if(!mf[i])mf[i]=pr[++TT]=i;
        for(int j=1,p;j<=TT&&(p=pr[j]*i)<=LIM;++j){
            mf[p]=pr[j];
            if(pr[j]^mf[i]);
            else {break;}
        }
    }
}

//phi 欧拉函数,小于x且与x互质的数的个数
void sieve(){
    For(i,2,LIM){
        if(!mf[i])mf[i]=pr[++TT]=i,phi[i]=i-1;
        for(int j=1,p;j<=TT&&(p=pr[j]*i)<=LIM;++j){
            mf[p]=pr[j];
            if(pr[j]^mf[i])phi[p]=phi[i]*(pr[j]-1);
            else {phi[p]=phi[i]*pr[j];break;}
        }
    }
}

//mu 莫比乌斯函数
void sieve(){
    For(i,2,LIM){
        if(!mf[i])mf[i]=pr[++TT]=i,mu[i]=-1;
        for(int j=1,p;j<=TT&&(p=pr[j]*i)<=LIM;++j){
            mf[p]=pr[j];
            if(pr[j]^mf[i])mu[p]=-mu[i];
            else {mu[p]=0;break;}
        }
    }
}

//dn 约数个数
//pn 最小质因子的次数 
void sieve(){
    dn[1]=1;
    For(i,2,LIM){
        if(!mf[i])mf[i]=pr[++TT]=i,dn[i]=2,pn[i]=1;
        for(int j=1,p;j<=TT&&(p=pr[j]*i)<=LIM;++j){
            mf[p]=pr[j];
            if(pr[j]^mf[i])	dn[p]=dn[i]<<1,pn[p]=1;
            else{dn[p]=dn[i]/(pn[i]+1)*(pn[i]+2),pn[p]=pn[i]+1;break;}
        }
    }
}

//ps 最小质因数的幂次和 
//s 约数和 
void sieve(){
    For(i,2,LIM){
        if(!mf[i])mf[i]=pr[++TT]=i,s[i]=ps[i]=i+1;
        for(int j=1,p;j<=TT&&(p=pr[j]*i)<=LIM;++j){
            mf[p]=pr[j];
            if(pr[j]^mf[i])ps[p]=pr[j]+1,s[p]=ps[i]*(pr[j]+1);
            else {ps[p]=ps[i]*pr[j]+1,s[p]=s[i]*(ps[i]*p+1)/ps[i];break;}
        }
    }
}

杜教筛

//需先筛出phi与mu
unordered_map<int,ll> ansmu,ansphi;
int get_mu(int x){
    if(x<=LIM) return mu[x];
    if(ansmu.count(x)) return ansmu[x];
    int ans=1;
    for(int l=2,r;(r<(1<<31)-1)&&l<=x;l=r+1)
    {
        r=x/(x/l);
        ans-=(r-l+1)*get_mu(x/l);
    }
    return ansmu[x]=ans;
}
ll get_phi(int x){
    if(x<=LIM) return phi[x];
    if(ansphi.count(x)) return ansphi[x];
    ll ans=0;
    for(int l=2,r;(r<(1<<31)-1)&&l<=x;l=r+1)
    {
        r=x/(x/l);
        ans+=(r-l+1)*get_phi(x/l);
    }
    return ansphi[x]=(ll)x*(x+1ll)/2ll-ans;
}