由图可知，一个人无法被看到时，当且仅当有 人与原点 的斜率与他相同，且在他之前。
∴一个人可以被看到，设其斜率为y/x，当且仅当y/x不可再约分，即gcd(x,y)=1。
考虑将图按对角线划分开，两部分对称，
对其中的下半部分来说，枚举x，其所对应的y值(y<x)有几个与它互质的，则其对答案的贡献就是几。
这个值显然就是phi(x)，所以枚举phi(x)，将它们加起来即可。
1 #include<cstdio> 2 using namespace std; 3 int n,phi[40001]; 4 //bool get_phi(const int &x)//求单个数的phi 5 //{ 6 // int ans=n; 7 // for(int i=2;i*i<=x;i++) 8 // if(n%i==0) 9 // { 10 // ans=ans/i*(i-1); 11 // while(n%i==0) n%=i; 12 // } 13 // if(n>1) ans=ans/n*(n-1); 14 //} 15 void phi_table() 16 { 17 phi[1]=1;//规定phi(1)=1; 18 for(int i=2;i<=n;i++) 19 if(!phi[i])//若i是质数(类似筛法的思想) 20 for(int j=i;j<=n;j+=i)//i一定是j的质因数 21 { 22 if(!phi[j]) phi[j]=j; 23 phi[j]=phi[j]/i*(i-1); 24 } 25 } 26 int main() 27 { 28 scanf("%d",&n); 29 if(n==2) printf("3 "); 30 else if(n==1) puts("0"); 31 else 32 { 33 long long ans=0; 34 phi_table(); 35 for(int i=1;i<n;i++) ans+=(long long)phi[i]; 36 printf("%lld ",ans<<1|1); 37 } 38 return 0; 39 }