向大（hei）佬（e）*学（di）习（tou）
Description
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在，C君希望你告诉他队伍整齐时能看到的学生人数。
Input
共一个数N。
Output
共一个数，即C君应看到的学生人数。
Sample Input
4
Sample Output
9
HINT
【数据规模和约定】 对于 100% 的数据，1 ≤ N ≤ 40000
一眼看去没有思路啊！O_O
先根据数据范围来看，o（n*n）必爆无疑，最多就是o（n*√n），当然，o（n）也是可以的。
这道题由组内的另外两位同（da）学（lao）用他们华尔街的狼之嗅觉立即发现了本质所在。蒟蒻的我就再理一遍思路（数论渣渣的我T_T）
如果我们把c君的位置设为(0,0)，建立直角坐标系的话，我们很容易发现：同在一个斜率上的点只能有一个被看到。那又能怎样呢？
再想想，P（x，y）和P0（x*k，y*k）即在同一直线上。那么，当x、y互质时，P点就能被看到。
互质……好熟悉的东西啊……是什么呢……？
标题已经暴露了，就是欧拉函数！求一个和就是了！！
于是蒟蒻去复（xin）习（xue）了一遍欧拉筛，把这道题调过了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=40000+5;
int n;
int phi[N],prime[N],sz=1,mark[N],sum=0;
void oula(){
memset(prime,0,sizeof(prime));
memset(mark,0,sizeof(mark));
for(int i=2;i<=n-1;i++){
if(!mark[i]){
prime[sz++]=i;
phi[i]=i-1;
sum+=phi[i];
}//背错啦 >_<
for(int j=1;j<sz&&i*prime[j]<=n-1;j++){
mark[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
sum+=phi[i*prime[j]];
break;
}else{
phi[i*prime[j]]=phi[i]*(prime[j]-1);
sum+=phi[i*prime[j]];
}
}
}
}
int main(){
scanf("%d",&n);
oula();
if(n!=1) printf("%d",sum*2+3);
else printf("0");
return 0;
}总结：
数论的知识看起来高大上不实用，然而数学无处不在。这道题算是拓宽眼界长知识了，世界真的好大