UVA 1393 Highways：網格城市中的高速公路計數與數論解法

問題重述

m×n 的矩形網格城市，原有橫向 m 條路、縱向 n 條路連接同行/同列城市。需新增高速公路（穿過兩個或以上城市的直線），使任意兩城市直接相連（同行/同列已連通，無需新建）。求需新建的高速公路條數（共線城市算一條）。

幾何轉化與數論本質

新高速公路對應：至少穿過兩個網格點、非水平非垂直的直線。等價於計算：在 (m-1)×(n-1) 的矩形區域內，有多少條不同斜率的直線段（以最簡分數表示斜率），並考慮平移後的不同位置。

核心公式推導

設網格大小為 (n-1) × (m-1)（即點陣的寬高）。一條直線由向量 (dx, dy) 確定，其中 gcd(dx, dy) = 1（最簡向量）。對於固定向量 (dx, dy)，其在網格內可平移的位置數為 (n - dx) * (m - dy)。總條數為所有互質向量對的位置數之和，再乘以 2（對稱斜率正負）。

定義 dp[i][j] 為 1≤x≤i, 1≤y≤j 且 gcd(x,y)=1 的點對數（即最簡向量數）。則：

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + (gcd(i,j)==1)

對於 n×m 網格，答案為：

ans[n][m] = 2 * Σ_{i=1}^{n-1} Σ_{j=1}^{m-1} dp[i][j] - dp[i/2][j/2]

其中減去 dp[i/2][j/2] 是為去除重複計數的向量（如 (2,2) 非最簡，但其最簡形式 (1,1) 已計入）。

預處理與查詢

因 n,m ≤ 300，可預處理 dp 和 ans 兩個 300×300 表，單次查詢 O(1)。代碼採用動態規劃填表，利用容斥原理避免重複計數。

關鍵代碼片段

const int MAXN = 310;
ll dp[MAXN][MAXN], ans[MAXN][MAXN];

void init() {
    for (int i = 1; i <= 300; ++i)
        for (int j = 1; j <= 300; ++j)
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + (__gcd(i,j)==1);

    for (int i = 1; i <= 300; ++i)
        for (int j = 1; j <= 300; ++j)
            ans[i][j] = ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1] + dp[i][j] - dp[i>>1][j>>1];
}

int main() {
    init();
    int n, m;
    while (scanf("%d%d", &n, &m) && n+m)
        printf("%lld\n", ans[n-1][m-1] * 2);
    return 0;
}

總結

本題將幾何計數問題轉化為數論前綴和問題，通過 gcd 判斷最簡向量，利用二維前綴和與容斥原理預處理答案，體現了「預處理換查詢」與「數論在組合幾何中的應用」的經典思想。