BZOJ 2190仪仗队【欧拉函数】

问题的唯一难点就是如何表示队长能看到的人数？如果建系，队长所在的点为（0,0）分析几组数据就一目了然了，如果队长能看到的点为(m,n),那么gcd（m，n）=1即m n 互质或者是（0,1），（1,0）两点。证明很简单，如果gcd（m，n）=d 那么(m/d,n/d)必然会挡住点（m，n），所以gcd（m，n）=1是必然的。这样问题就划归到2到n-1有多少数互质。由于欧拉函数的意义是小于n的与n互质的数的个数，所以知道欧拉函数意义的人都能第一时间想到答案就是t=φ（2）+φ（3）+…+φ（n-1） ，如果点（m，n）可以被看到，根据对称性（n，m）也可以被看到，再加上(1,1)(由于(1,1)是唯一不具有对称性的点所以分开来考虑)（0,1），（1,0）三点，所以答案 ans=t*2+3 ，如果定义φ（1）=1 那么答案就是φ（1）+φ（2）+φ（3）+…+φ（n-1）+1了

#include<iostream>

#include<cstdio>

#include <math.h>

using namespace std;

int prime[20000]={0},t;

bool isprime(int k)

{

    for (int i=1;i<=t-1;i++)

     {

        if (k % prime[i]==0)return false;

     }

    return true;

}

int euler(int k)

{

         intnow=1,e=1,i;

         while(k!=1)

         {

                   for(i=now;i<=t-1;i++)

                   {

                            now++;

                            if(k % prime[i]==0)break;

                   }

       e=e*(prime[i]-1);k=k/prime[i];

       while (k % prime[i]==0)

                   {

                            e=e*prime[i];

                            k=k/prime[i];

                   }

         }

         returne;

}

int main()

{

         t=2;

   int m,n,i,ans=0;

   scanf("%d",&n);

   prime[1]=2;

   

   for (i=2;i<=40000;i++)

    {

       m=i*2-1;

        if (isprime(m))

       {

           prime[t]=m;

           t++;

       }

    }

         for(i=1;i<=n-1;i++)

         {

                   ans+=euler(i);

         }

         ans=ans*2+1;

   printf("%d",ans);

   return 0;

}