有一个结论 一个点(x,y)到原点 经过gcd(x,y)个点 自己试一下就知道了
于是这题只要求一下$(\sum_{i=1}^{n-1}phi(i)*2)+1$就好了 n的范围很小没必要用线性筛
#include <cstdio> #include <algorithm> using namespace std; const int N=40010; int p[N],phi[N],n,vis[N],ans; int main(){ scanf("%d",&n); phi[1]=p[1]=1; for(int i=2;i<=n;i++) if(!vis[i]){ p[i]=1; phi[i]=i-1; for(int j=2;j*i<=n;j++){ if(!phi[i*j]) phi[i*j]=i*j; vis[i*j]=1; phi[i*j]=phi[i*j]*(i-1)/i; } } for(int i=1;i<n;i++) ans+=phi[i]*2; printf("%d",ans+1); return 0; }