HDU 1222: Wolf and Rabbit - 最大公約數判斷安全洞

問題描述

山上有 n 個洞（編號 0~n-1）。狼從 0 號洞開始，每隔 m 個洞鑽一次（即訪問 0, m, 2m, ... 模 n）。兔子藏在未被狼訪問的洞才安全。給定 m, n (0 < m, n < 2147483648)，判斷是否存在安全洞。輸出 "YES"（存在）或 "NO"（不存在）。

數學洞察

狼訪問的洞編號集合為 { k·m mod n | k = 0,1,2,... }。這是一個模 n 的循環子群，其大小為 n / gcd(n, m)。若 gcd(n, m) = 1，子群大小為 n，狼會訪問所有洞，兔子無安全洞（輸出 "NO"）；否則存在安全洞（輸出 "YES"）。

特例：m = n = 1 時，gcd=1，狼只訪問 0 號洞，但 n=1 只有 0 號洞，故無安全洞，邏輯一致。

算法實現

使用非遞歸歐幾里得算法計算 gcd，避免遞歸深度導致棧溢出或超時。讀入測試案例數 k，循環讀取 n, m，判斷 gcd(n,m)==1 輸出 "NO" 否則 "YES"。

完整代碼

#include <cstdio>

int gcd(int n, int m) {
    while (m != 0) {
        int t = n % m;
        n = m;
        m = t;
    }
    return n;
}

int main() {
    int k;
    scanf("%d", &k);
    while (k--) {
        int n, m;
        scanf("%d%d", &n, &m);
        printf("%s\n", gcd(n, m) == 1 ? "NO" : "YES");
    }
    return 0;
}