做烂了的欧拉函数,怎么就爆零惹/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);
}