擴(kuò)展歐幾里德算法用來(lái)在已知和
的情況下彬坏，求等式
的一組可行解，該算法思路如下：
- 若
膝晾，則有
栓始，
是一組可行解
- 若
，則設(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;
}
