作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在，C君希望你告诉他队伍整齐时能看到的学生人数。
共一个数N。
共一个数，即C君应看到的学生人数。
【数据规模和约定】 对于 100% 的数据，1 ≤ N ≤ 40000
这题laj去年一定做过【思考.jpg】欧拉函数裸题
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=40005; 5 int n,phi[MAX],ans; 6 void eular(){ 7 int i,j; 8 for (i=1;i<MAX;i++) phi[i]=i; 9 for (i=2;i<MAX;i+=2) phi[i]/=2; 10 for (i=3;i<MAX;i+=2) 11 if (phi[i]==i) 12 for (j=i;j<MAX;j+=i) 13 phi[j]=phi[j]/i*(i-1); 14 } 15 int main(){ 16 freopen ("millitry.in","r",stdin);freopen ("millitry.out","w",stdout); 17 int i,j; 18 scanf("%d",&n); 19 eular(); 20 for (i=1;i<n;i++) ans+=phi[i]; 21 printf("%d",ans*2+1); 22 return 0; 23 }
BZOJ-2190: [SDOI2008]仪仗队 (欧拉函数)
原文：http://www.cnblogs.com/keximeiruguo/p/7774874.html