最大公约数由$gcd(a,b) = gcd(b,a%b)$ 辗转相除法得到,

贝祖定理

存在整数a,b ,那么一定存在整数x,y,使得 $ax+by = gcd(a,b)$

• 可以判断$ax + by = gcd(a,b)$是否有解,或者$ax + by = m$ 且 $m = k * gcd(a,b)$
• 通过求gcd时 推x,y
• 首先是一组特解x = 1 y = 0

假设在辗转求gcd时满足一组
$bx+(a%b)y$ (注意到此时a=b b=a%b**,后面会解释)

(在$c++$中 a%b = a-(a/b)*b )

带入上式中$b*x+{a-(a/b)*b}*y$ ->

$bx+ay-(a/b)by$->

$ay+b{x-(a/b)y}$. **将此式对比原式***

$ax+by = gcd(a,b)$

得到了x,y的递推方程

• $x = y$
• $y = {x-(a/b)*y}$
• 代码表示就为

  int temp = y;
  y = x - (a/b) * y;
  x = temp;

• 还要注意到带入的式子$b*x+(a%b)*y$ (此时a = b b = a%b)
• 所以我们在递推x,y时,当前一步求的x,y是在下一步中得到,因为下一步a == b , b == a % b,所以写在递归回溯的地方

#include <iostream>

using namespace std;
 
int exgcd(int a,int b,int& x,int& y) {//扩展欧几里得算法

    if(b == 0) {
        x = 1;
		y = 0;
        return a;  //到达递归边界开始向上一层返回
    }
    int r = exgcd(b,a%b,x,y); // 在满足 ax + by -> bx + (a%b)y -> bx+(a-a/b*b)y -> ay + b(x - a/by) 
    int temp = y;    //保存一下 y, 
    y = x - (a/b) * y;
    x = temp; 
    return r;     // 在求gcd的时候将 x,y 也通过递推求出 
}
int gcd(int a,int b) {
	while (b != 0) {
		int temp = a;
		a = b;
		b = temp % b;
	}
//	cout << "a " << a << "b " << b << endl; 
	return a;
}
int main() {
	while (1) {
		int a,b;
		int x = 0,y = 0;
		cin >> a >> b;
		cout << "gcd: " << gcd(a,b) << endl;
		exgcd(a,b,x,y);
		cout << "x = " << x << "y = " << y << endl; 
	}
	return 0;
}