ZOJ 3609 Modular Inverse：擴展歐幾里得算法求模逆元

題目大意

給定 a, m (0 < a,m ≤ 1000)，求最小正整數 x 滿足 a*x ≡ 1 (mod m)。若不存在輸出 Not Exist。多測試用例 T ≤ 2000。

數學原理

a*x ≡ 1 (mod m) 有解 ⇔ gcd(a, m) = 1。解為 a 模 m 的逆元。使用擴展歐幾里得算法求解 a*x + m*y = gcd(a,m)，若 gcd=1 則 x 即為逆元（調整為正數）。

擴展歐幾里得模板

#include 
using namespace std;

void exgcd(int a, int b, int& d, int& x, int& y) {
    if (!b) { d = a; x = 1; y = 0; }
    else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int a, m; cin >> a >> m;
        int d, x, y;
        exgcd(a, m, d, x, y);
        if (d == 1) {
            x = (x % m + m) % m;  // 調整為最小正整數
            cout << x << '\n';
        } else {
            cout << "Not Exist\n";
        }
    }
    return 0;
}

複雜度與細節

• 時間：O(log min(a,m)) 每測試用例，極快。
• 調整負數：(x % m + m) % m 保證結果在 [0, m-1]，0 時輸出 m（但題目要求最小正整數，x=0 理論上不會出現，因 a*x≡1）。
• 輸入範圍小，無需優化 IO，但加上 ios::sync_with_stdio(false) 更穩妥。

擴展：模線性方程組

同樣模板可解 a*x ≡ b (mod m)：先求 d=gcd(a,m)，若 b%d!=0 無解；否則縮約為 (a/d)*x ≡ b/d (mod m/d) 求逆元後乘 b/d。本題為 b=1 特例。