擴(kuò)展歐幾里德算法用來在已知和的情況下，求等式的一組可行解，該算法思路如下：

1. 若，則有，是一組可行解
2. 若，則設(shè)遞歸求等式的一組可行解。設(shè)求得的可行解為，則有。又，且，故有。則，為原等式的一組可行解。

擴(kuò)展歐幾里德算法的實(shí)現(xiàn)代碼如下：

int ex_gcd(int a, int b, int & x, int & y){
    // ax + by = gcd(a,b) = r
    if(!b){
        x = 1; y = 0;
        return a;
    }
    int r = ex_gcd(b, a%b, x, y);
    int t = x; x = y; y = t-a/b*y;
    return r;
}

附上一道練習(xí)題：洛谷P1082 同余方程。

解題思路：求關(guān)于的同余方程的解，即相當(dāng)于求的解，又和必定互質(zhì)，故相當(dāng)于求的解，可以使用擴(kuò)展歐幾里德算法。

AC代碼：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int ex_gcd(int a, int b, int & x, int & y){
    // ax + by = gcd(a,b) = r
    if(!b){
        x = 1; y = 0;
        return a;
    }
    int r = ex_gcd(b, a%b, x, y);
    int t = x; x = y; y = t-a/b*y;
    return r;
}
int main(){
    int a, b, x, y;
    cin >> a >> b;
    ex_gcd(a, b, x, y);
    cout << (x%b+b)%b << endl;
}