zcmimi's blog

前置知识: 狄利克雷卷积

求积性函数f的前缀和:

S(n)=\sum_{i=1}^nf(i)

大部分题目都是可以线性筛的,可是某些丧心病狂的出题人会: n\le 10^{12}!

这时候需要用杜教筛了

我们构造另外一个积性函数g,那么

\sum_{i=1}^n(g * f) \\ =\sum_{i=1}^n\sum_{d|i}g(d)f(\frac id) \\ =\sum_{d=1}^ng(d)\sum_{d|i}f(\frac id) \\ =\sum_{d=1}^ng(d)\sum_{i=1}^{\frac nd}f(i) \\ =\sum_{d=1}^ng(d)S(\frac nd)

容斥一下,那么

g(1)S(n) \\ =\sum_{d=1}^ng(d)S(\frac nd)-\sum_{d=2}^ng(d)S(\frac nd) \\ =\sum_{i=1}^n(f * g)(i)-\sum_{i=2}^ng(i)S(\frac ni)

可以发现,前半部分是狄利克雷卷积的前缀和的形式,后半部分可以数论分块

最终可以优化到O(n^{\frac 23})

那么如何选好积性函数g呢?

莫比乌斯函数\mu

如果我们选择g=1(1\mu互为逆元,1 * \mu = \epsilon)

1(1)S(n)=S(n) \\ =\sum_{i=1}^n \epsilon(i)-\sum_{i=2}^n1(i)S(\frac ni) \\ =1-\sum_{i=2}^nS(\frac ni)

后半部分数论分块即可

欧拉函数\varphi

还是选取g=1

\varphi *1 = Id

1(1)S(n)=S(n) \\ =\sum_{i=1}^n Id(i)-\sum_{i=2}^n1(i)S(\frac ni) \\ =\frac{n(n+1)}2-\sum_{i=2}^nS(\frac ni)

前半部分直接得出,后半部分数论分块

代码

LG 4213 【模板】杜教筛(Sum)

#include<bits/stdc++.h>
typedef long long ll;
#pragma GCC optimize(3)
#define il __inline__ __attribute__ ((always_inline))
const int N=5000000;
int mu[N+11],pri[N+1];
ll phi[N+11];
bool b[N+11];
il void init(){
    mu[1]=phi[1]=1;
    int cnt=0;
    for(int i=2;i<=N;++i){
        if(!b[i])pri[++cnt]=i,mu[i]=-1,phi[i]=i-1;
        for(int j=1;j<=cnt&&i*pri[j]<=N;++j){
            b[i*pri[j]]=1;
            if(i%pri[j])mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*(pri[j]-1);
            else{phi[i*pri[j]]=phi[i]*pri[j];break;}
        }
    }
    for(int i=2;i<=N;++i)mu[i]+=mu[i-1],phi[i]+=phi[i-1];
}
const int P=1000007;
struct hash{
    int cnt=0,head[P];
    struct edge{int to,nxt;ll w;}e[P];
    il void add(int x,int y,ll w){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;e[cnt].w=w;}
    il void ins(int x,ll v){add(x%P,x,v);}
    il ll ask(int x){for(int i=head[x%P];i;i=e[i].nxt)if(e[i].to==x)return e[i].w;return 1ll<<63;}
}SP,SM;
ll PHI(int n){
    if(n<=N)return phi[n];
    ll t=SP.ask(n);if(t!=(1ll<<63))return t;
    ll res=1ll*n*(n+1)/2;
    for(ll l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        res-=PHI(n/l)*(r-l+1);
    }
    SP.ins(n,res);
    return res;
}
ll MU(int n){
    if(n<=N)return mu[n];
    ll t=SM.ask(n);if(t!=(1ll<<63))return t;
    ll res=1;
    for(ll l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        res-=MU(n/l)*(r-l+1);
    }
    SM.ins(n,res);
    return res;
}
int main(){
    init();
    int T,n;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%lld %lld\n",PHI(n),MU(n));
    }
}
杜教筛
comment评论
Search
search