首页 > 代码库 > [SDOI2008]仪仗队
[SDOI2008]仪仗队
题目链接
题目以左下角C君为0,0点 会发现C君能看到的人横纵坐标都是质数（不会证明，强行找规律），还有一点就是对称性，可以看到(2,1)点那么必然能看到(1,2)点。
那么结论就出来了:
1 -> n-1之间与phi值加和*2+1
1 #include <cstdio> 2 using namespace std; 3 int x,phi[100005],ans=1; 4 void phi_table(int n,int *phi) 5 { 6 for(int i=2;i<=n;i++) phi[i]=0; //初始化 7 phi[1]=1; 8 for(int i=2;i<=n;i++) 9 { 10 if(!phi[i]) 11 for(int j=i;j<=n;j+=i) 12 { 13 if(!phi[j]) phi[j]=j; 14 phi[j]=phi[j]/i*(i-1); 15 } 16 ans+=phi[i]; //加和 17 } 18 }19 int main(){20 scanf("%d",&x);21 if(x==1){22 printf("0");23 }24 else {25 phi_table(x-1,phi);26 printf("%d",ans*2+1);27 }28 return 0;29 }
[SDOI2008]仪仗队
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。