可见的点

在一个平面直角坐标系的第一象限内，如果一个点 $(x,y)$ 与原点 $(0,0)$ 的连线中没有通过其他任何点，则称该点在原点处是可见的。

例如，点 $(4,2)$ 就是不可见的，因为它与原点的连线会通过点 $(2,1)$。

部分可见点与原点的连线如下图所示：

编写一个程序，计算给定整数 $N$ 的情况下，满足 $0 leq x, y leq N$ 的可见点 $(x, y)$ 的数量（可见点不包括原点）。

输入格式

第一行包含整数 $C$，表示共有 $C$ 组测试数据。

每组测试数据占一行，包含一个整数 $N$。

输出格式

每组测试数据的输出占据一行。

应包括：测试数据的编号（从 $1$ 开始），该组测试数据对应的 $N$ 以及可见点的数量。

同行数据之间用空格隔开。

数据范围

$1 leq N,C leq 1000$

输入样例：

4
2
4
5
231

输出样例：

1 2 5
2 4 13
3 5 21
4 231 32549

解题思路

　　题目等价于问从$(0, 0)$处射处一条光线，能够射到多少个点？其中，当一条光线射到一个点后会把后面的点都挡住。

　　由于光线都从$(0,0)$处射出，因此每一条直线可以看成$y = kx$，因此所有的点都会在某一条直线上。而如果一个点$(x_0, y_0)$能够被射到，此时$(x_0, y_0)$所在的直线为$y = frac{y_0}{x_0}x$，那么意味着是这条直线上的第一个点（该点的左下方不存在在同一条直线上的点），等价于$x_0$与$y_0$互质。假设$x_0$与$y_0$不互质，$gcd(x_0, y_0) = d > 1$，那么$(frac{x_0}{d}, frac{y_0}{d})$也在直线上且在$(x_0, y_0)$的左下方，即$(x_0, y_0)$会被$(frac{x_0}{d}, frac{y_0}{d})$挡住，就矛盾了。

　　因此问题就变成了有多少个数对$(x, y)$满足$gcd(x, y) = 1$。

　　统计的方法是，先画出$y = x$，很明显$y = x$上的点都不满足条件，同时直线上下两个部分是对称的，下部分有多少个那么上部分就有多少个，因此这里只统计下部分的答案。$x$从$1$枚举每一列，首先第$1$列中与$1$互质的点有$2$个，第$2$列中与$2$互质的点有$1$个，第$3$列中与$3$互质的点有$2$个，以此类推。也就是对于第$i$列求$1 sim i$种与$i$互质的数有多少个，这就是欧拉函数$varphi(i)$。因此最终答案就是$2 cdot sumlimits_{i = 1}^{n}{varphi(i)} + 1$，加$1$是加上对角线上$(1, 1)$这个点。

　　AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1010;
 5 
 6 int primes[N], cnt;
 7 bool vis[N];
 8 int phi[N];
 9 
10 void get_prime(int n) {
11     phi[1] = 1;
12     for (int i = 2; i <= n; i++) {
13         if (!vis[i]) primes[cnt++] = i, phi[i] = i - 1;
14         for (int j = 0; primes[j] <= n / i; j++) {
15             vis[primes[j] * i] = true;
16             if (i % primes[j] == 0) {
17                 phi[primes[j] * i] = phi[i] * primes[j];
18                 break;
19             }
20             phi[primes[j] * i] = phi[i] * (primes[j] - 1);
21         }
22     }
23 }
24 
25 int main() {
26     get_prime(N - 1);
27     int m;
28     scanf("%d", &m);
29     for (int u = 1; u <= m; u++) {
30         int n;
31         scanf("%d", &n);
32         int ret = 1;
33         for (int i = 1; i <= n; i++) {
34             ret += phi[i] * 2;
35         }
36         printf("%d %d %dn", u, n, ret);
37     }
38     
39 }

参考资料

　　AcWing 201. 可见的点（算法提高课）：https://www.acwing.com/video/694/