杜教筛学习笔记

我太菜了所以现在才写杜教筛模板题Orz

问题

给定$n$($n\leq10^{10}$),求
$$\sum \limits_{i=1}^{n}\varphi(i)$$和$$\sum \limits_{i=1}^n\mu(i)$$

Solution

$$\begin{split}\sum \limits_{i=1}^{n}(f* g)(i)
&=\sum \limits_{i=1}^n\sum \limits_{d|i}f(d)\cdot g(\frac{i}{d})\
&=\sum \limits_{d=1}^ng(d)\cdot \sum \limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\
&=\sum \limits_{d=1}^ng(d)\cdot S(\lfloor\frac{n}{d}\rfloor)
\end{split}$$
$$g(1)\cdot S(n)=\sum \limits_{i=1}^{n}(f* g)(i)-\sum \limits_{i=2}^ng(i)\cdot S(\lfloor\frac{n}{i}\rfloor)$$

将$\varphi *1=\text{id}$带入上式得$$S(n)=\frac{n\cdot (n+1)}{2}-\sum \limits_{i=2}^nS(\lfloor\frac{n}{i}\rfloor)$$

将$\mu * 1=\varepsilon$带入上式得$$S(n)=1-\sum \limits_{i=2}^n S(\lfloor\frac{n}{i}\rfloor)$$

线性筛预处理出一部分的$S$之后直接递归处理即可

感觉杜教筛比Min_25筛不知道简单到哪里去了

模板

Luogu P4213

#include <iostream>
#include <cstdio>
#include <unordered_map>

typedef long long LL;
const int MX=7300000;
LL Smu[MX+10], Sphi[MX+10];
int pri[MX/2+10];
bool isn_pri[MX+10];
std::unordered_map<LL, LL>mp_mu, mp_phi;

void get_pri(){
    Sphi[1]=Smu[1]=1;
    for(int i=2; i<=MX; i++){
        if(!isn_pri[i]) pri[++pri[0]]=i, Sphi[i]=i-1, Smu[i]=-1;
        for(int j=1; j<=pri[0] && i*pri[j]<=MX; j++){
            isn_pri[i*pri[j]]=true;
            if(i%pri[j]==0){
                Smu[i*pri[j]]=0, Sphi[i*pri[j]]=Sphi[i]*pri[j];
                break;
            }else Smu[i*pri[j]]=-Smu[i], Sphi[i*pri[j]]=Sphi[i]*(pri[j]-1);
        }
    }
    for(int i=1; i<=MX; i++) Smu[i]+=Smu[i-1], Sphi[i]+=Sphi[i-1];
}

LL Sum_mu(LL N){
    if(N<=MX) return Smu[N];
    if(mp_mu.find(N)!=mp_mu.end()) return mp_mu[N];
    LL ans=1;
    for(LL i=2, nxt; i<=N; i=nxt+1){
        nxt=N/(N/i);
        ans-=Sum_mu(N/i)*(nxt-i+1);
    }
    mp_mu[N]=ans;
    return ans;
}

LL Sum_phi(LL N){
    if(N<=MX) return Sphi[N];
    if(mp_phi.find(N)!=mp_phi.end()) return mp_phi[N];
    LL ans=N*(N+1)/2;
    for(LL i=2, nxt; i<=N; i=nxt+1){
        nxt=N/(N/i);
        ans-=Sum_phi(N/i)*(nxt-i+1);
    }
    mp_phi[N]=ans;
    return ans;
}

int main(){
    get_pri(); int T; LL N; scanf("%d", &T);
    while(T--){
        scanf("%lld", &N);
        printf("%lld %lld\n", Sum_phi(N), Sum_mu(N));
    }
    return 0;
}

其实啊,这份代码卡不过去最后一个点,一定是毒瘤出题人卡常数了

发表评论

电子邮件地址不会被公开。 必填项已用*标注