BZOJ2190 [SDOI2008]仪仗队（欧拉函数）

与HDU2841大同小异。

设左下角的点为(1,1)，如果(1,1)->(x,y)和(1,1)->(x’,y’)向量平行，那只有在前面的能被看见。然后就是求x-1、y-1不互质的数对个数。

而x或y等于1可以另外讨论一下，就是当n不等于1时就有两个，n等于1就特判一下。

那么就用欧拉函数计数了：枚举x-1，累加小于x-1与x-1互质的个数，即合法的y-1的个数；结果还要*2，因为还有一半对称的y-1>x-1的情况；此外x-1=y-1多算了一次，减去1即可。

 #include<cstdio>
 #include<cstring>
 using namespace std;
 #define MAXN 43210
 int phi[MAXN],prime[MAXN];
 bool vis[MAXN];
 void euler(){
     phi[]=;
     int tot=;
     for(int i=; i<MAXN; ++i){
         if(!vis[i]){
             prime[tot++]=i;
             phi[i]=i-;
         }
         for(int j=; j<tot; ++j){
             if(i*prime[j]>MAXN) break;
             vis[i*prime[j]]=;
             if(i%prime[j]==){
                 phi[i*prime[j]]=phi[i]*prime[j];
                 break;
             }else{
                 phi[i*prime[j]]=phi[i]*(prime[j]-);
             }
         }
     }
 }
 int main(){
     euler();
     int n;
     scanf("%d",&n);
     if(n==){
         putchar('');
         return ;
     }
     int res=;
     for(int i=; i<=n; ++i){
         res+=phi[i-]<<;
     }
     printf("%d",res-);
     return ;
 }