杜教筛

约 298 个字 75 行代码 预计阅读时间 2 分钟

杜教筛

求数论函数前缀和

复杂度

$O(n^{\frac 23})$

原理

设数论函数 $f$，其前缀和 $S(n)=\sum\limits_{i=1}^n f(i)$，另一数论函数 $g$

$\sum\limits_{i=1}^nf*g(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}f(i)g(\frac id)$

$=\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\frac ni\rfloor}f(j)g(i)$

$=\sum\limits_{i=1}^ng(i)\sum\limits_{j=1}^{\lfloor\frac ni\rfloor}f(j)$

$=\sum\limits_{i=1}^ng(i)S(\lfloor\frac ni\rfloor)$

$g(1)S(n)=\sum\limits_{i=1}^nf*g(i)-\sum\limits_{i=2}^ng(i)S(\lfloor\frac ni\rfloor)$

假如可以快速求 $\sum\limits_{i=1}^nf*g(i)$，数论分块求 $\sum\limits_{i=2}^ng(i)S(\lfloor\frac ni\rfloor)$，则 $S(n)$ 可求

线性筛预处理前 $n^{\frac 23}$，记忆化中间结果(map和um，洛谷数据测试二者差别不大)

莫比乌斯函数前缀和

$f=\mu$，$g=1$，$f*g=\epsilon$

$S(n)=1-\sum\limits_{i=2}^nS(\lfloor\frac ni\rfloor)$

const int N=1e8+3;
const int M=6e6;
bitset<N> v;
int p[M];
int mu[N];
void seive()
{
    int cnt=0;
    mu[1]=1;
    for(int i=2;i<N;++i)
    {
        if(!v[i])
        {
            p[cnt++]=i;
            mu[i]=-1;
        }
        for(int j=0;j < cnt && i*p[j] < N;++j)
        {
            v[i*p[j]]=1;
            if(!(i%p[j]))
                break;
            mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1;i<N;++i)
        summu[i]=summu[i-1]+mu[i];
}
struct Du
{
    map<ll,ll> mpmu;
    long long Smu(long long x)
    {
        if (x < N)
            return summu[x];
        if (mpmu.count(x))
            return mpmu[x];
        long long res = 1;
        for (long long l = 2, r; l <= x; l = r + 1)
        {
            r = x / (x / l);
            res -= Smu(x / l) * (r - l + 1);
        }
        return (mpmu[x] = res);
    }
}du;

欧拉函数前缀和

如果同时求欧拉函数前缀和，莫比乌斯函数前缀和用这个，如果单独求欧拉函数前缀和用下面那个

莫反求：

$\sum\limits_{i=1}^n\phi(i)=\sum\limits_{i=1}^n\mu(i)\lfloor\frac nd\rfloor^2$

long long Sphi(long long x)
{
    long long z,y=0,res =1;
    for (long long l = 1,r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        z=Smu(r);
        res += (z - y) * (x / l) * (x / l);
        y=z;
    }
    return res / 2;
}

杜教筛求：

$f=\phi$，$g=1$，$f*g=ID$

$S(n)=\frac{n(n+1)}2-\sum\limits_{i=2}^nS(\lfloor\frac ni\rfloor)$

struct Du
{
    map<ll,ll> mpphi;
    ll Sphi(int x)
    {
        if (x <N)
            return sumphi[x];
        if (mpphi.count(x))
            return mp[x];
        ll res = (x&1)?(x+1)/2*x:x/2*(x+1);//如果可能溢出用int128
        for (ll l = 2, r; l <= x; l = r + 1)
        {
            r = x / (x / l);
            res -= Sphi(x / l) * (r - l + 1);
        }
        return (mp[x] = res);
    }
}du;