二元gcd演算法如何求最大公因數

二元gcd算法，也稱為歐幾里得算法（Euclidean algorithm），是一種計算兩個整數的最大公約數（Greatest Common Divisor, GCD）的算法。這個算法是建立在輾轉相除法的基礎上的，它的時間複雜度為O(log(max(a, b)))，其中a和b是待求最大公約數的兩個整數。

以下是二元gcd算法的偽代碼：

function gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

這個算法的工作原理是：每次將b的值替換為a除以b的餘數，直到b為0，此時a就是a和b的最大公約數。這是因為，根據輾轉相除法，如果a除以b的餘數是c，那麼a和b的最大公約數就是b和c的最大公約數。

下面是一個使用二元gcd算法求兩個整數最大公約數的例子：

輸入：a = 120, b = 48

步驟：
1. 初始化 a = 120, b = 48
2. 計算 a % b = 120 % 48 = 72
3. 交換變數 a 和 b 的值，即 a = 48, b = 72
4. 計算 a % b = 48 % 72 = 24
5. 交換變數 a 和 b 的值，即 a = 72, b = 24
6. 計算 a % b = 72 % 24 = 48
7. 交換變數 a 和 b 的值，即 a = 24, b = 48
8. 計算 a % b = 24 % 48 = 0
9. 由於 b == 0，停止循環，輸出 a 的值

輸出：最大公約數是 24

這個算法不僅可以在O(log(max(a, b)))的時間內求出兩個整數的最大公約數，而且它還可以用來推導出線性丟番圖方程的整數解。