网上讲解可多了，我也刚学会？好像是会了就不讲了
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<string> #include<map> using namespace std; long long phi[160005]; map<int,long long>G; int n; void lcr() { int i,k,l,j,t; long long p; for(i=2;i<=16000;i++){ k=0;t=i;p=i; for(j=2;j<=sqrt(t);j++){ if(t%j==0)p=(p-p/j); while(t%j==0)t/=j; } if(t!=1)p=(p-p/t); phi[i]=p; phi[i]+=phi[i-1]; } } long long find(int x) { int i,r=x,l=2; long long ans=0; if(x<=16000)return phi[x]; if(G[x])return G[x]; ans=(long long)x*(x+1)/2; while(l<=x){ r=x/(x/l); if(x/l>16000)ans-=(long long)(r-l+1)*find(x/l); else ans-=(long long)(r-l+1)*phi[x/l]; l=r+1; } return G[x]=ans; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int i,j,k,l; scanf("%d",&n); phi[1]=1; lcr(); printf("%lld",find(n)); return 0; }