杜教筛

杜教筛

前置知识

积性函数：对于任意的(gcd(i,j)=1)，(f(i) imes f(j)=f(ij))。

完全积性函数：对于任意的(i,j)，(f(i) imes f(j)=f(ij))。

(epsilon(x)=[x==1])，(I(x)=1)，(id(x)=x)，(sigma_k(x)=sumlimits_{d|x}d^k)。

狄利克雷卷积

((f*g)(n)=sumlimits_{d|n}f(n)g(frac{n}{d}))。

推论：

1.(mu*I=epsilon)

证明：当(n=1)时上式显然为1，当(n>1)时，根据唯一分解定理，设(n=p_1^{a_1}p_2^{a_2}cdots p_k^{a_k})，根据(mu)的定义，若(a_i>1)则(mu(d))为0，则(sumlimits_{d|n}mu(d)=sumlimits_{i=0}^kinom{k}{i}(-1)^i=(1-1)^k=0)

2.(varphi*I=id)

证明：当(n=p^m)时，(sumlimits_{d|n}varphi(d)=varphi(1)+sumlimits_{i=1}^mvarphi(p^i)=1+sumlimits_{i=1}^m(p^i-p^{i-1})=p^m=n)

当(n)为任意整数时，令(n=prod p^m)，则((varphi*I)(prod p^m)=prod(varphi*I)(p)=prod p^m=n)

3.(mu*id=varphi)

证明：

莫比乌斯反演

若

则

证明：因为(g=(f*I))，所以(g*mu=f*I*mu=f*(I*mu)=f*epsilon=f)

杜教筛

杜教筛是用来快速求积性函数前缀和的方法。具体来说，我们设(S(n)=sumlimits_{i=1}^nf(i))，再找一个积性函数(g(x))，考虑((f*g))的前缀和

我们把(g(1)S(n))提出来，就是(g(1)S(n)=sumlimits_{i=1}^ng(i)S(leftlfloorfrac{n}{i} ight floor)-sumlimits_{i=2}^ng(i)S(leftlfloorfrac{n}{i} ight floor))，我们发现，前一项(sumlimits_{i=1}^ng(i)S(leftlfloorfrac{n}{i} ight floor))由前面推导可知为(sumlimits_{i=1}^n(f*g)(i))，于是得到了杜教筛的核心式子：

这就意味着，只要我们找到一个可以快速计算((f*g))的前缀和的(g(x))，我们就可以用数论分块递归求解(S(n))，时间复杂度是(O(n^{frac{3}{4}}))，如果我们预处理前(n^{frac{2}{3}})个答案，我们就可以把复杂度降到(O(n^{frac{2}{3}}))。

一些应用

1.求(mu)的前缀和

因为(mu*I=epsilon)，所以把(I(x))当做(g(x))即可，而且前缀和超好求。

代码：

inline int calcmu(int x){
    if(x<=M)return summu[x];
    if(mp.find(x)!=mp.end())return mp[x];
    int ans=1;
    for(int l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans=(ans-(r-l+1)%p*calcmu(x/l)%p)%p+p)%p;
    }
    return mp[x]=ans;
}

2.求(varphi)的前缀和

因为(varphi*I=id)，所以把(I(x))当做(g(x))即可。

代码：

inline int calcphi(int x){
    if(x<=M)return sumphi[x];
    if(mp.find(x)!=mp.end())return mp[x];
    int ans=x*(x+1)/2%p;
    for(int l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans=(ans-((r-l+1)%p*calcphi(x/l)%p)%p+p)%p;
    }
    return mp[x]=ans;
}

例题

1.P4213 【模板】杜教筛（Sum）

就是求(mu,varphi)的前缀和，直接套板子。

2.P3768 简单的数学题

题意：求(sumlimits_{i=1}^nsumlimits_{j=1}^nijgcd(i,j))

思路：

然后考虑怎么求前一项
令(f=mu*id*id)，(g=id*id)，则((f*g)(n)=sumlimits_{d|n}(varphi(d)d^2)(frac{n}{d})^2=n^3)，这样就又可以愉快套板子了。

inline int calc(int x){
    if(x<=M)return sumphi[x];
    if(mp.find(x)!=mp.end())return mp[x];
    int ans=S2(x);
    for(int l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans=(ans-((S1(r)-S1(l-1)+p)%p*calc(x/l)%p)%p+p)%p;
    }
    return mp[x]=ans;
}
inline int solve(){
    int ans=0;
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        ans=(ans+(calc(r)-calc(l-1)+p)%p*S2(n/l)%p)%p;
    }
    return ans;
}