HUDJ 3270 The Diophantine Equation：線性不定方程非負整數解判定

HUDJ 3270 The Diophantine Equation：判定 ax + by = c 是否有非負整數解

題目大意：多組輸入，每行形如 "ax + by = c"（a,b 為正整數，c 為整數，|c| < 1e6，a,b < 1e5）。若 a=1 則顯示 "x" 而非 "1x"。判斷是否存在非負整數解 (x≥0, y≥0)。輸出 "Yes." 或 "No."，每組後空行。

解題思路

方程 ax + by = c 有整數解 ⇔ gcd(a,b) | c。
進一步要求非負解：遍歷 x 從 0 到 c/a（若 c<0 則無非負解），檢查 (c - a*x) % b == 0。因 a,b ≤ 1e5，c ≤ 1e6，循環次數 ≤ 1e6/1 = 1e6，最多 100 組測試，暴力枚舉 x 完全來得及（實測幾十 ms）。
也可用擴展歐幾里得求一組特解，再推導通解範圍，但暴力更簡碼不易錯。

核心代碼

#include 
#include 
using namespace std;

int main() {
    char s1[20], s2[20]; char q, w; int c;
    while (cin >> s1 >> q >> s2 >> w >> c) {
        int a = 0, b = 0;
        for (int i = 0; i < (int)strlen(s1)-1; i++) a = a*10 + s1[i]-'0';
        for (int i = 0; i < (int)strlen(s2)-1; i++) b = b*10 + s2[i]-'0';
        if (a == 0) a = 1; // "x" 情況
        if (b == 0) b = 1; // "y" 情況
        bool ok = false;
        if (c >= 0) {
            for (int x = 0; x <= c/a; x++)
                if ((c - a*x) % b == 0) { ok = true; break; }
        }
        cout << (ok ? "Yes." : "No.") << "\n\n";
    }
    return 0;
}

輸入解析技巧

• 用 char s1[20], s2[20] 讀取 "ax"、"by" 字符串。
• 去掉末尾字母 'x'/'y' 解析係數。
• 利用 cin >> s1 >> q >> s2 >> w >> c 自動跳過 '+'、'=' 等分隔符。