仪仗队（欧拉函数）

仪仗队

来源：
2008年省队选拔赛山东
题目描述：
　　作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。
　　
　　现在，C君希望你告诉他队伍整齐时能看到的学生人数。
输入描述：
　　共一个数N。
输出描述：
　　共一个数，即C君应看到的学生人数。
样例输入：
4
样例输出：
9
数据范围及提示：
对于30% 的数据，1≤N≤1000
对于100% 的数据，1≤N≤40000
思路：
能被看到的点有一个特点：横、纵坐标互质，所以可以暴力枚举，但是一定会超时+爆内存。所以这里用到了欧拉函数。
r[i]存储1~i中与i互为质数的数的个数。

#include<iostream>
using namespace std;
const int maxn=40010;
int n,ans=1,r[maxn];
int main()
{
    cin>>n;n--;r[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!r[i])
        {
            for(int j=i;j<=n;j+=i)
            {
                if(!r[j])
                r[j]=j;
                r[j]=r[j]/i*(i-1);
            }
        }
        ans+=r[i];
    }
    cout<<ans*2+1;
    return 0;
}