杜教筛

杜教筛

莫比乌斯函数前缀和

const int __=5e6;  //n^(2/3)项

bool pri[__+5];
int mu[__+5],num[__+5];
ll sum[__+5];

void mobius()
{
    mu[1]=sum[1]=1;
    pri[1]=true;
    for(int i=2;i<=__;i++)
    {
        if(!pri[i])
        {
            num[++num[0]]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=num[0] && i*num[j]<=__;++j)
        {
            int &p=num[j];
            pri[i*p]=true;
            if(!(i%p)){mu[i*p]=0;break;}
            mu[i*p]=-mu[i];
        }
        sum[i]=sum[i-1]+mu[i];
    }
}

unordered_map<ll,ll>dp;

ll cal(ll x)
{
    if(x<=__)return sum[x];
    if(dp[x])return dp[x];
    ll res=1;
    for(ll l=2,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        res-=(r-l+1)*cal(x/l);
    }
    return dp[x]=res;
}

欧拉函数前缀和(取模)

const int __=5e6;
const int mod=1e9+7;
const int inv2=(mod+1)/2;

ll md(ll x)
{
    if(x<=-mod || x>=mod)
        x%=mod;
    if(x<0)x+=mod;
    return x;
}

int phi[__+5],num[__+5];
ll sum[__+5];

void euler()
{
    phi[1]=sum[1]=1;
    for(int i=2;i<=__;i++)
    {
        if(!phi[i])
        {
            num[++num[0]]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=num[0] && i*num[j]<=__;++j)
        {
            int &p=num[j];
            if(!(i%p))
            {
                phi[i*p]=phi[i]*p;
                break;
            }
            phi[i*p]=phi[i]*(p-1);
        }
        sum[i]=sum[i-1]+phi[i];
        if(sum[i]>=mod)sum[i]-=mod;
    }
}

unordered_map<ll,ll>dp;

ll cal(ll x)
{
    if(x<=__)return sum[x];
    if(dp[x])return dp[x];
    ll res=md(md((md(x)+1ll)*md(x))*inv2);
    for(ll l=2,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        res=md(res-md(md(r-l+1)*cal(x/l)));
    }
    return dp[x]=res;
}