扩展欧几里得

扩展欧几里德求这样一个问题：

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

其中，$a,b$ 给定，需要求出 $x$ 和 $y$。

我们知道

$$\gcd(a,b)=\gcd(b,a \bmod b)$$

所以，假设以递归的方式实现，得出上一步等式为：

$$bx'+y'(a \bmod b)=\gcd(b,a \bmod b)=\gcd(a,b)$$

展开：

$$bx'+y'(a-b\cdot\lfloor \frac{a}{b}\rfloor)=\gcd(a,b)$$

$$bx'+ay'-y'(b\cdot\lfloor \frac{a}{b}\rfloor)=\gcd(a,b)$$

将关于 $a$ 的放在左边，关于 $b$ 放在右边：

$$ay'+bx'-by'\cdot\lfloor \frac{a}{b}\rfloor=\gcd(a,b)$$

$$ay'+b\,(x'-y'\cdot\lfloor \frac{a}{b}\rfloor)=\gcd(a,b)$$

比较这个式子和开头式子，可得：

$$x=y'$$

$$y=x'-y'\cdot\lfloor \frac{a}{b}\rfloor$$

于是就可以递归啦！

顺带一提，当 $a=1,b=0$，也就是边界时，返回 $x'=1,y'=0$

code:

void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	int z=x;//z=x'
	x=y;
	y=z-y*(a/b);
}
//use & to return x and y
//void