模逆元求解：擴展歐幾里得算法解 ax ≡ 1 (mod m)

數學轉化

方程 a*x ≡ 1 (mod m) ⇔ 存在整數 y 使 a*x - m*y = 1。這是裴蹄方程，有解條件 gcd(a,m)=1，解模 m 唯一。

擴展歐幾里得算法

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    int r = exgcd(b, a % b, y, x); // 遞歸交換 x,y
    y -= x * (a / b);
    return r;
}

完整解題流程

1. 讀入 a, m。若 m == 1，答案為 1（模 1 所有數同餘 0，但題目約定最小正解 1）。
2. 若 gcd(a,m) != 1，輸出 "Not Exist"。
3. 調用 exgcd(a, m, x, y) 得到特解 x。
4. 調整 x = (x % m + m) % m 使其落在 [0, m-1]。若 x==0 則 x=m（但模逆元通常取 1..m-1）。
5. 輸出 x。

代碼示例

#include <cstdio>
#include <algorithm>
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    int r = exgcd(b, a%b, y, x);
    y -= x * (a / b);
    return r;
}
int main() {
    int T, a, m; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &a, &m);
        if (m == 1) { puts("1"); continue; }
        if (gcd(a, m) != 1) { puts("Not Exist"); continue; }
        int x, y; exgcd(a, m, x, y);
        x = (x % m + m) % m;
        printf("%d\n", x);
    }
    return 0;
}

應用場景

RSA 解密密鑰生成、中國剩餘定理合併同餘方程、模除法運算（a/b mod m = a * b^{-1} mod m）。