【bzoj2190】[SDOI2008]仪仗队

2190: [SDOI2008]仪仗队

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 2638 Solved: 1674
[Submit][Status][Discuss]

Description

　　作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。　　　　现在，C君希望你告诉他队伍整齐时能看到的学生人数。

Input

　　共一个数N。

Output

　　共一个数，即C君应看到的学生人数。

Sample Input

Sample Output

【题解】

显然，能看见的点坐标应满足gcd(x,y)=1

用欧拉函数解之即可。最后别忘了加上(0,0)这个点

 /*************

   bzoj 2190

   by chty

   2016.11.3

 *************/

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<ctime>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 #define MAXN 40010

 int n,ans,phi[MAXN],check[MAXN],prime[MAXN];

 inline int read()

 {

     int x=,f=;  char ch=getchar();

     while(!isdigit(ch))  {if(ch=='-')  f=-;  ch=getchar();}

     while(isdigit(ch))  {x=x*+ch-'';  ch=getchar();}

     return x*f;

 }

 void get()

 {

     phi[]=;  int cnt=;

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

     {

         if(!check[i])  {prime[++cnt]=i; phi[i]=i-;}

         for(int j=;j<=cnt&&prime[j]*i<=n;j++)

         {

             check[prime[j]*i]=;

             if(i%prime[j])  phi[i*prime[j]]=phi[i]*(prime[j]-);

             else {phi[i*prime[j]]=phi[i]*prime[j];  break;}

         }

     }

 }

 int main()

 {

     freopen("cin.in","r",stdin);

     freopen("cout.out","w",stdout);

     n=read();  get();

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

     printf("%d\n",ans*+);

     return ;

 }

巴特西