首页 > 代码库 > 【SDOI2008】【P1377】仪仗队
【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是(x,y)和左下角的水平距离
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 int n; 8 int kang[41000],phi[41000],zhi[410000],ztop=0; 9 void shai(){10 memset(kang,0,sizeof(kang));11 phi[1]=1;12 for(int i=2;i<=n;i++){13 if(!kang[i]){ phi[i]=i-1; zhi[++ztop]=i;}14 for(int j=1;j<=ztop && i*zhi[j]<=n;j++){15 kang[i*zhi[j]]=true;16 if(i%zhi[j]==0){ phi[i*zhi[j]]=phi[i]*zhi[j]; break;}17 phi[i*zhi[j]]=phi[i]*phi[zhi[j]];18 }19 }20 }21 int main(){//freopen("ddd.in","r",stdin);22 cin>>n;23 shai();24 long long bowl=0;25 for(int i=1;i<n;i++) bowl+=phi[i];26 cout<<bowl*2+1<<endl;27 return 0;28 }
【SDOI2008】【P1377】仪仗队
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。