[SDOI2008]仪仗队

OJ题号：

BZOJ2190、洛谷2158

思路：

欧拉$varphi$函数的应用。
经过观察可发现，可以被观察到的点，其坐标$(x,y)$中$x$和$y$必定互质。
那么，除去左边第一列、下边最后一行的点，左上角、右下角总共能看到的点数是$displaystyle{sum_{1leq i<n}}varphi(i)$。
用一种类似于素数筛的方法即可求出所有的欧拉$varphi$函数值。
注意最后对角线会重复算，需要减去一次，并加上左边第一列、下边最后一行共两次，最后答案是$ans imes 2+1$。

 1 #include<cstdio>
 2 #include<cstring>
 3 int main() {
 4     int n;
 5     scanf("%d",&n);
 6     int phi[n];
 7     memset(phi,0,sizeof phi);
 8     int ans=phi[1]=1;
 9     for(int i=2;i<n;i++) {
10         if(!phi[i]) {
11             for(int j=i;j<n;j+=i) {
12                 if(!phi[j]) {
13                     phi[j]=j;
14                 }
15                 phi[j]=phi[j]/i*(i-1);
16             }
17         }
18         ans+=phi[i];
19     }
20     printf("%d
",ans<<1|1);
21     return 0;
22 }