Description
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
Input
共一个数N。
Output
共一个数，即C君应看到的学生人数。
Sample Input
4
Sample Output
9
HINT
【数据规模和约定】 对于 100% 的数据，1 ≤ N ≤ 40000
很容易想到把方阵对折，这样只要处理一半。假设当前有(i-1)*(i-1)的方阵已经计算出答案，考虑加入第i层。它应该是长这样的：
对于第i层，我们只要考虑枚举j，使坐标(i,j)不会和以前出现过的点重复。
坐标(i,j)不会和以前出现过的点重复的充要条件是：不存在一个点(m,n)，使k(m-1)=(i-1)且k(n-1)=(j-1)。
即求有多少个j<=i使gcd(i-1,j-1)=1
于是用欧拉函数phi乱搞
#include<cstdio>
#include<cmath>
int phi[40001];
int n,ans;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
void shai()
{
for (int i=1;i<=n;i++)
phi[i]=i;
for (int i=2;i<=n;i++)
if (phi[i]==i)
for (int j=1;j<=n/i;j++)
phi[i*j]=phi[i*j]/i*(i-1);
}
int main()
{
n=read();
if (n==1) {printf("1");return 0;}
shai();
for (int i=1;i<n;i++) ans+=phi[i];
printf("%d",2*ans+1);
}