原题链接：https://www.luogu.com.cn/problem/P2158
题意解读：n*n个点组成的方阵中，最左下角的点能看到多少点。
解题思路：
设左下角点的坐标是(0, 0)，设从0点能看到的点是(x, y)，对于看不到的点必然可以通过将(x, y)同时扩大一定倍数得到(xd, yd)
这样一来，看不到的点必然其x、y坐标的GCD不为1，能看到的点的坐标GCD为1，也就是x、y互质的点是能被看到的。
要统计方阵中一共有多少个互质的点，可以分两块来看，上三角、下三角，由于对称性，只用统计一边即可，再乘2加1，加1是因为对角线能看到1个。
对于上三角，一共有多少个点的坐标互质呢？
问题可以转化成计算从上到下每一个行互质的点数：
第1行：纵坐标n-1，横坐标1~n-1，结果就是phi(n-1)
第2行：纵坐标n-2，横坐标1~n-2，结果就是phi(n-2)
。。。
第n-1行：纵坐标1，横坐标1，结果就是phi(1)
因此，只需要用线性筛将1~n-1的phi值都预处理出来，然后加在一起即可。最后*2+1。
注意如果方阵是1*1,则一个都看不到。
100分代码：
#include <bits/stdc++.h>
using namespace std;const int N = 40005;
int primes[N], cnt, phi[N];
bool vis[N];
int n;int main()
{cin >> n;for(int i = 1; i <= n; i++) phi[i] = i;for(int i = 2; i <= n; i++){ if(!vis[i]){primes[++cnt] = i;vis[i] = true;phi[i] = i - 1;}for(int j = 1; j <= cnt; j++){if(i * primes[j] > n) break;vis[i * primes[j]] = true;if(i % primes[j] == 0){phi[i * primes[j]] = phi[i] * primes[j];break;}else{phi[i * primes[j]] = phi[i] * (primes[j] - 1);}}}int ans = 0;if(n > 1){for(int i = 1; i < n; i++) ans += phi[i];ans = ans * 2 + 1;} cout << ans;return 0;
}