杜教筛学习笔记

杜教筛用于在亚线性的时间复杂度内求解一个数论函数的前缀和。

给定一数论函数 \(f\) ，求 \(s(n)=\sum_{i=1}^nf(i)\) 。对于 \(n\) 很大，我们就不能用线性筛来处理了，考虑非线性的做法。

我们构造一个函数 \(g\) ，将 \(f\) 和 \(g\) 进行狄利克雷卷积

把 \(d=1\) 这一项提出来，得

我们发现，如果我们构造的函数 \(g\) 满足便于求解 \(g\) 和 \(f*g\) 的前缀和，对后面一部分式子进行数论分块，就可以快速的出答案了。

实现过程首先预处理出 \(i\leq n^{\frac{2}{3}}\) 的 \(s(i)\) 的值，整体复杂度就是 \(o(n^{\frac{2}{3}})\) 。

常用卷积关系

代码实现如下

inline void Init() {
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(!pd[i]) p[++idx]=i, mu[i]=-1;
        for(int j=1;j<=idx && i*p[j]<N;j++) {
            pd[i*p[j]]=1;
            if(i%p[j]==0) { mu[i*p[j]]=0; break; }
            else mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1;i<N;i++) mu[i]+=mu[i-1];
} 

inline LL Get_mu(LL n) {
    if(n<N) return mu[n];
    else if(mp_mu[n]) return mp_mu[n];
    LL res=1;
    for(LL i=2,j;i<=n;i=j+1) {
        j=n/(n/i);
        res-=1LL*(j-i+1)*Get_mu(n/i);
    }
    return mp_mu[n]=res;
}

inline LL Get_phi(LL n) {
    LL res=0;
    for(LL i=1,j;i<=n;i=j+1) {
        j=n/(n/i);
        res+=1LL*(n/i)*(n/i)*(Get_mu(j)-Get_mu(i-1));
    }
    return (res-1)/2LL+1;
}

原文地址：http://www.cnblogs.com/oscaryangzj/p/16845822.html