数学筛法

有的时候怕忘记，写篇小博客记录一下。

线性筛素数

inline void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt && i*prime[j];j++)
        {
            vis[i*prime[j]]=1;
            if(!(i%prime[j])) break;
        }
    }
    return;
}

线性筛求欧拉函数

inline void init(int n)
{
    memset(vis,0,sizeof(vis));
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) {prime[++cnt]=vis[i]=i，phi[i]=i-1;}
        for(int j=1;j<=cnt && i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=prime[j];
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
        }
    }
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i];
    return;
}

线性筛求莫比乌斯函数

inline void init(int n)
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) {mu[i]=-1;prime[++cnt]=i;}
        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;}
            else mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];
    return;
}

线性筛求约数个数

用 \(d_i\) 表示 \(i\) 的约数个数，\(num_i\) 表示 \(i\) 的最小质因子出现次数。

inline void init(int n)
{
    d[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) 
        {
            prime[++cnt]=i;
            d[i]=2,num[i]=1;
        }
        for(int j=1;j<=cnt && i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(!(i%prime[j]))
            {
                num[i*prime[j]]=num[i]+1;
                d[i*prime[j]]=d[i]/num[i*prime[j]]*(num[i*prime[j]]+1);
                break;
            }
            else num[i*prime[j]]=1,d[i*prime[j]]=d[i]*2;
        }
    }
    return;
}

线性筛求约数和

用 \(s_i\) 表示 \(i\) 的约数和，\(g_i\) 表示 \(i\) 的最小质因子的 \(p^0+p^1+p^2+\dots +p^k\).

inline void init(int n)
{
    s[1]=g[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) vis[i]=1,prime[++cnt]=i,g[i]=i+1,s[i]=i+1;
        for(int j=1;j<=cnt && i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(!(i%prime[j]))
            {
                g[i*prime[j]]=g[i]*prime[j]+1;
                s[i*prime[j]]=s[i]/g[i]*g[i*prime[j]];
                break;
            }
            else
            {
                s[i*prime[j]]=s[i]*s[prime[j]];
                g[i*prime[j]]=prime[j]+1;
            }
        }
    }
    return;
}