POJ - 3090. Visible Lattice Points

#题面

难度：提高+/省选-

#题目描述

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

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

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

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

#输入格式

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

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

#输出格式

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

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

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

#输入输出样例

样例输入 #1

4
2
4
5
231

样例输出 #1

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

#数据范围与约定

对于 $100\%$ 的数据，$1 \le N, C \le 1000$。

#思路

分析题目可得，除了 $(1, 0)$、$(0, 1)$ 和 $(1, 1)$ 三个点，其他点都只能在满足 $\gcd(x, y) = 1$ 时被看到。

然后还可以发现能看到的点是沿着 $(0, 0) - (n, n)$ 这条直线对称的，所以只计算其中一半然后再将答案乘 $2$ 即可。

可以发现满足上述性质的点的数量恰好是 $\sum_{i = 2}^{n} \varphi(i)$。

所以最终答案为 $3 + 2 \times \sum_{i = 2}^{n} \varphi(i)$。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

const int N = 1005;

int _t, n, phi[N], ans;

int main() {
    // Init
    for (int i = 2; i <= 1000; i++) {
        phi[i] = i;
    }
    for (int i = 2; i <= 1000; i++) {
        if (phi[i] == i) {
            for (int j = i; j <= 1000; j += i) {
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
    // End: Init

    cin >> _t;
    for (int t = 1; t <= _t; t++) {
        ans = 0;
        cin >> n;
        for (int i = 2; i <= n; i++) {
            ans += phi[i];
        }
        cout << t << ' ' << n << ' ' << ans * 2 + 3 << endl;
    }
    return 0;
}