扩展欧几里得-exgcd

在讲解扩展欧几里得之前我们先回顾下辗转相除法:

当$a\%b==0$的时候$b$即为所求最大公约数

好了切入正题:
简单地来说exgcd函数求解的是$ax+by=gcd(a,b)$的最小正整数解。根据数论的相关知识,一定存在一组解$x,y$使得$ax+by=gcd(a,b)$当且仅当$a$与$b$互质的时候。那就来谈谈具体如何来求解吧。
根据辗转相除法的内容$gcd(a,b)=gcd(b,a\%b)$我们可以得到:
又由于$a\%b=a- \lfloor a\div b\rfloor\times b$
在计算机中 $a\%b= \lfloor a\div b\rfloor\times b=a/b*b$ 所以 $$bx_2+a\%by_2=bx_2+(a-a/b*b)y_2$$ 将等式①变形得:$$ax_1+b(y_1+a/ b*y_2)=ay_2+bx_2$$ 因为等式左右两边结构相同我们可以解得:$$\begin{cases}x_1=y_2\\y_1=x_2-a/b*y_2\end{cases}$$ 在扩展欧几里得算法的最后一步即$b=0$的时候,显然有一对整数$x=1,y=0$使得$$a*1+b*0=gcd(a,0)$$
那么我们就可以通过编程实现exgcd了,请仔细体验下代码的精妙之处:

1
2
3
4
5
6
7
8
9
10
int exgcd(int a, int b, int &x, int &y) {
if(b) {
int d = exgcd(b, a%b, y, x);
y -= a / b * x;
} else {
x = 1;
y = 0;
return a;
}
}