题意:链接方法:线性欧拉解析:首先列一下表达式gcd(x,y)=z(z是素数并且x,y<=n).然后我们可以得到什么呢？gcd(x/z,y/z)=1;不妨令y>=x则可以得到我们要的答案就是而max(y/z)就是max(n/z)；所以只需要枚举一下质数z随便搞一下就好了，最好用前缀和记录HINT：前缀和写树状数组的都是(*)代码：正常人做法1.1susing namespace std;typedef long long ll;int n,tot;int prime[N];int phi[N];ll sum[N];int f[N];void sieve(){phi[1]=1;sum[1]=1;for(int i=2;i<=n;i++){if(!f[i]){prime[++tot]=i;phi[i]=i-1;}for(int j=1;j<=tot,i*prime[j]<=n;j++){f[i*prime[j]]=1;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}sum[i]=sum[i-1]+phi[i];}}int main(){scanf(“%d”,&n);sieve();ll print=0;for(int i=1;i<=tot;i++){int up=n/prime[i];print+=sum[up];}printf(“%lld\n”,print*2-tot);}树状数组4.8susing namespace std;typedef long long ll;int n,tot;int prime[N];int phi[N];ll sum[N];int f[N];&(-x);}void update(int x,int p){while(x<=n){sum[x]+=p;x+=lowbit(x);}}ll getsum(int x){ll ret=0;while(x){ret+=sum[x];x-=lowbit(x);}return ret;}void sieve(){phi[1]=1;update(1,1);for(int i=2;i<=n;i++){if(!f[i]){prime[++tot]=i;phi[i]=i-1;update(i,phi[i]);}for(int j=1;j<=tot,i*prime[j]<=n;j++){f[i*prime[j]]=1;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];update(i*prime[j],phi[i*prime[j]]);break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];update(i*prime[j],phi[i*prime[j]]);}}}}int main(){scanf(“%d”,&n);sieve();ll print=0;for(int i=1;i<=tot;i++){int up=n/prime[i];print+=getsum(up);}printf(“%lld\n”,print*2-tot);}
，多对自己说“我能行，我一定可以”，
