NYOJ 144 小珂的苦惱 - 擴展 GCD 判斷二元一次方程整數解

題目

給 a, b, c (≠0)，判斷 ax + by = c 是否存在整數解。多組測資 T ≤ 10⁶。

數學依據

裴蜀定理：ax + by = gcd(a,b) 必有整數解。推論：ax + by = c 有整數解 當且僅當 c % gcd(a,b) == 0。

算法

1. 輾轉相除法求 g = gcd(a,b)，O(log min(a,b))。
2. 判斷 c % g == 0，輸出 Yes/No。

代碼 (C++ 快速 IO)

#include 
using namespace std;

int gcd(int a, int b) {
    while (b) { int r = a % b; a = b; b = r; }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int a, b, c; cin >> a >> b >> c;
        cout << (c % gcd(a,b) == 0 ? "Yes" : "No") << '\n';
    }
    return 0;
}

複雜度

• 時間：O(T log V)，V = max(|a|,|b|)。
• 空間：O(1)。

注意

• 題目保證 a,b,c ≠ 0，無需處理零除錯誤。
• 大量測資必開 ios::sync_with_stdio(false); cin.tie(nullptr);。