Time Limit: 10 Sec Memory Limit: 259 MB
Description
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
Input
共一个数N。
Output
共一个数，即C君应看到的学生人数。
Sample Input
4
Sample Output
9
HINT
【数据规模和约定】对于 100% 的数据，1 ≤ N ≤ 40000
简要题解:我们再此把上面的图再放一遍：
我们假设左下角为(0,0)点，右上角为(n-1,n-1)点。那么从(0,0)点引出了的“视线”一定是一个正比例函数，“视线”上的第一个整点（横纵坐标都是整数的点）一定满足gcd(x,y)=1。当然，有几个点不满足条件，就是(0,1)和(1,0)这两个在坐标轴上的点。
那么我们的任务就转化成判断(1 leq x leq n quad 1 leq y leq n)的范围内，有多少个(gcd(x,y)=1)即x,y互质。根据对称性，我们把原来的正方形剖成两半等腰直角三角形，这样我们可以只统计右下三角形，保证(1 leq x < y leq n)，当然我们需要把对角线上的点特判一下，不过也就(1,1)，记一次即可。这样我们只需要统计(1 leq x < y leq n)，有多少(gcd(x,y)=1)。这不就是欧拉函数(varphi(y))的定义吗？
因此，我们只需要计算(3+sum limits_{i=2}^n varphi(i))即可。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=40000+7;
int n,np[maxn],phi[maxn],p[maxn],tot,ans;
inline void Prime_Table(){
np[0]=np[1]=1;
for(register int i=2;i<=n;++i){
if(!np[i])phi[i]=i-1,p[++tot]=i;
for(register int j=1;j<=tot&&i*p[j]<=n;++j){
np[i*p[j]]=1;
if(i%p[j])phi[i*p[j]]=phi[i]*(p[j]-1);//错误笔记：把这一行和下一行的phi[i*p[j]] 写成了 p[i*p[j]]
else{phi[i*p[j]]=phi[i]*p[j];break;}//错误笔记：这里应该是 p[i*p[j]]=phi[i]*p[j];而不是 p[i*p[j]]=phi[i]*p[j]-1;
}
}
}
int main(){
scanf("%d",&n);--n;Prime_Table();ans=3;
for(register int i=2;i<=n;++i)ans+=2*phi[i];
printf("%d
",ans);
}