作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在，C君希望你告诉他队伍整齐时能看到的学生人数。
共一个数N。
共一个数，即C君应看到的学生人数。
终于A了！这个欧拉函数搞得我头昏脑涨！！
简介（欧拉函数的值 ）通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3
那么φ（12）=12*（1-1/2）*(1-1/3)=4）经过观察发现这个仪仗队是对称的，我们可以求出左下角那一面；
再仔细观察，若(x,y)是可以看见的点，那么他们满足gcd(x,y)=1。
这时候，欧拉函数有用武之地啦！问题转化为：给定N，有数对(i,j),满足i>j,2<i<=n,2<=j<n，且gcd(i,j)=1，求数对的个数。（当然，结果要乘2，加1）我们枚举i（3-N），再枚举i的所有质因子k，用欧拉函数求出j的个数。
代码：
#include<stdio.h>
#include<cmath>
using namespace std;
long zhi[40001],n,cnt,i,j;
double ans;
long long max;
bool ok(long k) //判断质数
{
for (long i=2;i<=trunc(sqrt(k));i++)
if (k%i==0) return false;
return true;
}
int main()
{
scanf("%ld",&n);n--; //N是人数个数，而边数要减1.
zhi[1]=2;cnt=1;
for (i=3;i<=n;i++)
if (ok(i)) zhi[++cnt]=i; //预处理质数表
for (i=1;i<=n;i++)
{
ans=i;
for (j=1;j<=cnt;j++)
if (i%zhi[j]==0) ans=ans*(zhi[j]-1)/zhi[j]; //欧拉函数
max+=ans;
}
if (n<=0) printf("0"); //特判0,1情况
else printf("%ld",max*2+1);
//scanf("%ld",&n);
return 0;
}原文：http://blog.csdn.net/jiangshibiao/article/details/19703723