bzoj2190: [SDOI2008]仪仗队（欧拉）

2190: [SDOI2008]仪仗队

题目：传送门

题解：

　　 跟着企鹅大佬做题！

　　 自己瞎搞搞就OK，不难发现，如果以C作为原点建立平面直角坐标系，那么在这个坐标系中，坐标为(x,y)且GCD(x,y)==1的点肯定看不见

　　 其实就相当于要求两点之间连线的斜率唯一。。。也就是1-n-1的不同的互质点对

　　 那就可以用欧拉来做，直接求1-n-1的phi值（因为x或y最多达到n-1）

　　 不过最后要输出phi[n-1]*2+3,因为phi只求出一边，而坐标系是对称的，+3则是因为一开始左下角的三条边欧拉不会求（因为欧拉从2开始啊）

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int phi[];//x,y均小于等于n的不同的互质数对的个数

 int n;

 void get_phi()

 {

     for(int i=;i<=n;i++)phi[i]=i;

     for(int i=;i<=n;i++)

     {

         if(phi[i]==i)

             for(int j=i;j<=n;j+=i)

                 phi[j]-=phi[j]/i;

         phi[i]+=phi[i-];

     }

 }

 int main()

 {

     scanf("%d",&n);n--;

     get_phi();printf("%d\n",phi[n]*+);

     return ;

 }