歐幾里得演算法

歐幾里德演算法也叫輾轉相除法，用來求 ，它運用了一個性質：

對於 ，（）。

Proof.
，所以 、 的公因數和 、 是一樣的。

從這個性質可以推出 ，遞迴直到 。

因為 ，所以每過兩次 會變小至少一半（），得出這個演算法的時間複雜度是 。

1
2
3
4
5
6
7
8

int gcd(int a, int b){
    while(b > 0){
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

實作上可以用迴圈，常數比較小，不過在 C++ 裡不用自己寫，可以用 __gcd(a,b)。

擴展歐幾里德演算法

擴展歐幾里德演算法用來求 的整數解。

貝祖定理：

對於整數 ， 有解若且唯若 。

由此可知只要 不是 的倍數就無解。有解的話，令 ，可以先找 的解，擴展歐幾里德演算法的作法是嘗試從輾轉相除法的遞迴式，做出一個長得差不多的式子：

得出 、，所以先求 就可以算出 ，終止條件一樣是當 時，回傳 即可。

1
2
3
4
5

pii exgcd(int a, int b){
    if(b == 0) return mp(1, 0);
    pii ans = exgcd(b, a % b);
    return mp(ans.S, ans.F - a / b * ans.S);
}

最後得到的答案只要乘上 倍，就可以變成 的答案。

其他的解

擴展歐幾里德演算法只會拿到其中一組解。先來看看兩組解會有什麼關係：有兩組整數解 、，我們知道

因為 和 互質，因此 、，也就是說有了一組解 後，其他解都可以寫成 ，。

負數的狀況

這裡有一些小小細節，因為係數常常有可能是負的，所以特別討論一下負數的狀況。在上面的式子裡面，寫的都是 ，但是程式碼裡的 a % b 實際上是 a - a / b * b，而 a / b 是向零取整而非向下取整。在不同的除法（向下、向下、向零）定義下，gcd(a,b) 給出的結果正負會不一樣。

要避免這個問題發生，就要確保 gcd 和 exgcd 的遞迴過程完全一樣。如果好好照上面那樣寫，並且算 用的是 __gcd 就不會出任何問題，但是如果你在 exgcd 不小心把 a / b 變成向下取整，還繼續用 __gcd 就會出事了。

如果不喜歡有負數的話，可以把負號移到變數上，例如 可以變成 。

解的範圍

另外還有溢位的問題，事實上可以不用擔心運算過程發生溢位。因為貝祖定理其實還告訴我們：

一定存在恰兩組整數解 滿足 、，而且擴展歐幾里德演算法得出的是其中一組。

所以不只可以知道運算過程數字都會保持在一個範圍內，而且還可以知道如果你想要拿到最小正數解之類的，只要把得到的解移動幾次就可以了。