做烂了的欧拉函数，怎么就爆零惹/kel

用的杜教筛来计算欧拉函数的前缀和QAQ

dalao康康吧/dk/dk/dk

#include<unordered_map>
#include<cstdio>
typedef long long ll;
const int M=2e4;
int top,pri[M];
ll n,ans,phi[M|5];bool zhi[M|5];
std::unordered_map<int,ll>Sphi;
ll GetSphi(int n){
    if(n<=M)return phi[n];
    if(Sphi.find(n)!=Sphi.end())return Sphi[n];
    ll ans=1ll*n*(n+1)>>1;
    for(int L=2,R;L<=n;L=R+1){
        R=n/(n/L);
        ans-=(R-L+1)*GetSphi(n/L);
    }
    return Sphi[n]=ans;
}
signed main(){
    int i,j,x;
    scanf("%lld",&n);
    zhi[1]=phi[1]=1;
    for(i=2;i<=M;++i){
        if(!zhi[i])phi[i]=(pri[++top]=i)-1;
        for(j=1;j<=top&&(x=i*pri[j])<=M;++j){
            zhi[x]=1;
            if(!(i%pri[j])){
                phi[x]=phi[i]*pri[j];
                break;
            }
            phi[x]=phi[i]*(pri[j]-1);
        }
        phi[i]+=phi[i-1];
    }
    for(int L=1,R;L<=n;L=R+1){
        R=n/(n/L);
        ans+=(GetSphi(R)-GetSphi(L-1))*(n/L)*(n/L);
    }
    printf("%lld",(ans-(n*(n+1)>>1))>>1);
}