POJ 3090 Visible Lattice Points：可見格點計數與歐拉函數應用

POJ 3090 Visible Lattice Points：可見格點計數

在第一象限（包含坐標軸）中，從原點 (0,0) 出發，若連接 (x,y) 的線段不經過其他格點，則稱 (x,y) 為可見格點。給定 N（1 ≤ N ≤ 1000），求 0 ≤ x,y ≤ N 範圍內可見格點的數量（不含原點）。

數學洞察

格點 (x,y) 可見 ⇔ gcd(x,y) = 1。問題轉化為計算 1 ≤ x,y ≤ N 中互質對數，再加上坐標軸上的點 (1,0) 和 (0,1)。利用對稱性，只需計算 x > y 的情況再乘 2，加上對角線 x=y=1 的情況。

動態規劃預處理

預處理 b[i] 表示大小為 i 的正方形內可見點數。遞推公式：b[i] = b[i-1] + 2 * sum_{j=1}^{i-1} [gcd(i,j)==1]。利用陣列 a[x][y] 標記斜率 y/x 是否已出現（即 gcd(x,y) 是否為 1 的等價類）。

代碼實現

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[1005][1005];
int b[1005];
int gcd(int a, int b) {
    if (a < b) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a % b);
}
int main() {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    b[1] = 3; b[2] = 5;
    a[1][1] = a[1][2] = a[2][2] = a[2][1] = 1;
    for (int i = 3; i <= 1000; i++) {
        int sum = 0;
        for (int j = 1; j < i; j++) {
            int c = gcd(i, j);
            if (!a[i/c][j/c]) {
                sum++;
                a[i][j] = 1;
            }
        }
        b[i] = b[i-1] + sum * 2;
    }
    int t, n, cnt = 1;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("%d %d %d\n", cnt++, n, b[n]);
    }
    return 0;
}

預處理 O(N² log N)，查詢 O(1)，完美應對多測試用例。