题目描述
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)
。 
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
输入输出格式
输入格式：
共一个数N
输出格式：
共一个数，即C君应看到的学生人数。
输入输出样例
输入样例#1：
4
输出样例#1：
9
说明
【数据规模和约定】
对于 100% 的数据，1 ≤ N ≤ 40000
/* 不知道那个数学老师了 上数学课的时候一直在强调数形结合 这个题目的思路就可以从图形中得到启发 发现无论图形多大，总是有三个点是能看到的，那就是上边右上边 和右边的三个 然后发现图形沿左下到右上的对角线对称 所以我们求出一个三角形乘以二就能得到答案了 大致是下面的样子 初始矩阵 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0代表三角形 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 将三角形扣出来仔细观察 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 能看到的为 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 1 是不是看出了什么 竖着的每一列的个数不就是这一列加一的欧拉函数么 然后就能够模拟求出来了 */ #include<cstdio> #include<algorithm> #include<iostream> using namespace std; int phi(int x) { int ans = x; for(int i = 2;i * i <= x;i++) { if(x % i == 0) { ans = ans / i * (i - 1); } while(x % i == 0)x /= i; } if(x > 1) ans = ans / x * (x - 1); return ans; } int main() { int n; scanf("%d",&n); long long ans = 0;//特殊的三个 for(int i = 2;i <= n - 1;i++) ans += phi(i); cout << ans * 2 + 3; return 0; }