Skip to content

POJ - 3090. Visible Lattice Points

题解679 字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

本题有以下几种解法:


题面

难度:提高+/省选-

题目描述

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

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

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

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

输入格式

第一行包含整数 CC,表示共有 CC 组测试数据。

每组测试数据占一行,包含一个整数 NN

输出格式

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

应包括:测试数据的编号(从 11 开始),该组测试数据对应的 NN 以及可见点的数量。

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

输入输出样例

样例输入 #1

4
2
4
5
231

样例输出 #1

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

数据范围与约定

对于 100%100\% 的数据,1N,C10001 \le N, C \le 1000

思路

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

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

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

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

代码

#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;
}