【SDOI2008】【P1377】仪仗队

欧拉函数的应用

原题：

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

1<=N<=40000

首先可以把图沿着左下角到右上角内条对角线对折一下，两边是一样的所以只要求出其中一边*2+1即可（因为对角线还有一个，所以+1）

每一边怎么求呐

可以发现所有能看到的点都满足gcd(x,y)==1

然后就是求1<=x<=n-1的phi的和了

为什么呐

首先y一定要比x小，否则就跑到另一边去了（上面对折了↑），然后gcd(x,y)还要==1，就是比x小且与x互质的数的个数，也是欧拉函数的定义，所以直接求phi的和即可

这里需要注意，左下角的坐标要设成0（这也是上面求的是1<=x<=n-1的phi的和↑的原因），因为这样才能保证x-左下角的值是(x,y)和左下角的水平距离

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 int n;

 int kang[],phi[],zhi[],ztop=;

 void shai(){

     memset(kang,,sizeof(kang));

     phi[]=;

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

         if(!kang[i]){  phi[i]=i-;  zhi[++ztop]=i;}

         for(int j=;j<=ztop && i*zhi[j]<=n;j++){

             kang[i*zhi[j]]=true;

             if(i%zhi[j]==){  phi[i*zhi[j]]=phi[i]*zhi[j];  break;}

             phi[i*zhi[j]]=phi[i]*phi[zhi[j]];

         }

     }

 }

 int main(){//freopen("ddd.in","r",stdin);

     cin>>n;

     shai();

     long long bowl=;

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

     cout<<bowl*+<<endl;

     return ;

 }

巴特西

【SDOI2008】【P1377】仪仗队

最新文章

热门文章