【题目大意】
给定一个n×n的点方阵，求站在左下角的点能看到的点数
注意同一条直线上只能看到一个点
【思路分析】
因为是一个方阵，所以可以对称地算，那么对于半个方阵，这里假设是左上的半个方阵，能看到的点的个数要满足这样的条件
1.x<y
因为是左上的半个方阵，并且x=y的一直线上的点要额外计算
2.gcd(x,y)即x与y互质
这是为了保证一直线上只能看到一个点
容易发现，在满足条件的情况下，这样的x个数恰好等于φ(y)
还需要注意的一点是，最左边一列，最下面一行，还有x=y这条直线上一共可以看到三个点，所以要额外计算
于是最后的答案Ans=3+2*$sum_{i=2}^{n}varphi[i]$
【代码实现】
1 #include<bits/stdc++.h> 2 #define go(i,a,b) for(register int i=a;i<=b;i++) 3 using namespace std; 4 const int N=40002; 5 int v[N],prime[N],phi[N]; 6 int n; 7 int fr(){ 8 int w=0,q=1; 9 char ch=getchar(); 10 while(ch<'0'||ch>'9'){ 11 if(ch=='-') q=-1; 12 ch=getchar(); 13 } 14 while(ch>='0'&&ch<='9') 15 w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); 16 return w*q; 17 } 18 void work(){ 19 memset(v,0,sizeof(v)); 20 int num=0; 21 go(i,2,n){ 22 if(v[i]==0){//如果i没有被标记过,那就是质数 23 v[i]=i,prime[++num]=i; 24 phi[i]=i-1;//性质2 25 } 26 go(j,1,num){ 27 if(prime[j]>v[i]||prime[j]>n/i) break; 28 v[i*prime[j]]=prime[j]; 29 phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]); 30 //性质8和性质9的结合 31 } 32 } 33 } 34 int ans=0; 35 int main(){ 36 n=fr();n--; 37 //这里要注意一下题目的bug,你可以认为输入的是点数但实际上是看格子 38 if(n==0) {printf("0 ");return 0;} 39 work(); 40 go(i,2,n) 41 ans+=phi[i]; 42 ans*=2;ans+=3; 43 printf("%d ",ans); 44 return 0; 45 }