深入淺出exgcd

一、exgcd的概念

exgcd，全稱為extended Euclidean algorithm，即擴展歐幾里得算法。顧名思義，它是一種擴展版的歐幾里得算法，可用於求解兩個整數之間最大公約數以及對應的貝祖等式係數。通常情況下，我們只需要求解最大公約數即可滿足需求，而對於貝祖等式係數，其用處比較廣泛，如在密碼學中用於求解模反元素等問題。

二、求解最大公約數

求解兩個整數的最大公約數問題是exgcd應用最廣泛的領域之一。具體做法如下：

// exgcd求解最大公約數
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return gcd;
}

上述代碼使用了遞歸的方式來求解最大公約數。需要注意的是，遞歸邊界為$b=0$的情況，此時$x$和$y$各自為1和0，最大公約數為$a$。

三、求解貝祖等式

在exgcd求解最大公約數過程中，我們也同時求解了貝祖等式係數$x$和$y$。對於貝祖等式$a\times x+b\times y=gcd(a,b)$而言，我們可以將其視為一種線性方程，進而通過倍增、高斯消元、矩陣快速冪等方式進行求解。下面是使用倍增法的求解方式：

// a*x+b*y=gcd(a,b)的通解
pair<int, int> exgcd(int a, int b) {
    int x = 1, y = 0, lastx = 0, lasty = 1;
    while (b != 0) {
        int quotient = a / b;
        int temp = b;
        b = a % b;
        a = temp;
        temp = x;
        x = lastx - quotient * x;
        lastx = temp;
        temp = y;
        y = lasty - quotient * y;
        lasty = temp;
    }
    return make_pair(lastx, lasty);
}

當然，在實際代碼編寫過程中，我們可能只需要一個解即可，因此也可以進行優化，將遞增過程替換為單次求解。下面是對上述代碼的小改進：

// a*x+b*y=gcd(a,b)的獨特解
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return gcd;
}
// 求解a*x+b*y=gcd(a,b)的解x
int exgcd(int a, int b, int gcd) {
    int x, y;
    exgcd(a, b, x, y);
    return (x % (b / gcd) + b / gcd) % (b / gcd);
}

四、應用舉例

在具體應用中，exgcd的用處比較廣泛，如以下幾個場景：

情景1： 判斷兩個整數是否互質。

當兩個整數互質時，其最大公約數為1。因此我們只需要判斷exgcd返回的最大公約數是否為1即可。下面是相應的代碼實現：

// 判斷兩個整數是否互質
bool is_coprime(int a, int b) {
    return exgcd(a, b) == 1;
}

情景2： 解決同餘方程組。

同餘方程組是以模同餘關係為基礎的方程組。通常我們可以通過中國剩餘定理進行求解，而exgcd則是其最基礎的組成部分。以例1為例：

例1: 求解同餘方程組

$x\equiv 2(mod\;3)$

$x\equiv 3(mod\;5)$

通常情況下，我們可以使用中國剩餘定理得到通解，但此處我們先使用exgcd求解該方程組：

pair<int, int> exgcd(int a, int b) {
    int x = 1, y = 0, lastx = 0, lasty = 1;
    while (b != 0) {
        int quotient = a / b;
        int temp = b;
        b = a % b;
        a = temp;
        temp = x;
        x = lastx - quotient * x;
        lastx = temp;
        temp = y;
        y = lasty - quotient * y;
        lasty = temp;
    }
    return make_pair(lastx, lasty);
}
// 求解同餘方程組x=a1(mod m1),x=a2(mod m2)的通解，時間複雜度O(log(m1+m2))
int exCRT(int a1, int m1, int a2, int m2) {
    int gcd = exgcd(m1, m2).first;
    int x = ((a2 - a1) % m2 + m2) % m2 * exgcd(m1 / gcd, m2 / gcd).first % (m2 / gcd) * m1 % m2 + a1;
    return gcd == 1 ? x : -1;
}

上述代碼實現了exgcd在求解同餘方程組中的應用，時間複雜度為$O(log(m1+m2))$。

總結

exgcd是解決數學問題的一種基礎工具，其應用範圍比較廣泛，通常用於求解最大公約數、貝祖等式、判斷兩個整數是否互質、解決同餘方程組等問題。同樣重要的是，掌握exgcd的理論知識，可以幫助我們更加深入理解相關算法、降低算法實現難度。本文從多個角度對exgcd做了詳細的闡述，並提供了相應的代碼實現，希望能夠幫助讀者更好地掌握這一重要的算法。