洛谷题单指南-进阶数论-P2158 [SDOI2008] 仪仗队

原题链接：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;
}