『扩展欧几里得算法 Extended Euclid』
2019-08-13


Euclid算法(gcd)

在学习扩展欧几里得算法之前,当然要复习一下欧几里得算法啦。众所周知,欧几里得算法又称gcd算法,辗转相除法,可以在(O(log_2b))时间内求解((a,b))(a,b的最大公约数)。其核心内容可以陈述为:((a,b)=(b,a\%b)),然后反复迭代该式缩小(a,b)规模,直到(b=0),得到a为最大公约数。

证明

设两数为(a b(b<a)),求它们最大公约数的步骤如下:用(b)(a),即(a/b=q…..r),得(a=bq+r)((0≤r<b),即为余数,(q)是这个除法的商)。若(r=0),则(b)(a)(b)的最大公约数,(a)(b)存在倍数关系。若(r≠0),则继续考虑。

首先,应该明白的一点是任何 (a)(b) 的公约数都是 (r) 的公约数。要想证明这一点,就要考虑把 (r) 写成 (r=a-bq)。现在,如果 (a)(b) 有一个公约数 (d),而且设 (a=sd , b=td), 那么 (r = sd-tdq = (s-tq)d)。因为这个式子中,所有的数(包括 (s-tq))都为整数,所以 (r) 可以被 (d) 整除。

对于所有的 (d) 的值,这都是正确的。所以 (a)(b) 的最大公约数也是 (b)(因为(b< a),所有取b继续运算才能不断缩小规模,直至两数有倍数关系) 和 (r) 的最大公约数。因此我们可以继续对 (b)(r) 进行上述取余的运算。这个过程在有限的重复后,可以最终得到 (r=0) 的结果,我们也就得到了 (a)(b) 的最大公约数

实现

(Code:)

inline int Euclid(int a,int b){return b==0?a:Eucild(b,a%b);}

Extended Euclid算法(exgcd)

那么接下来就是扩展欧几里得啦。正如其名,扩展欧几里得算法就是基于欧几里得算法的扩展运用。该算法用于解决一下模型的问题:

求解关于(x,y)的二元不定方程(ax+by=c)的整数解

在讲解算法之前,需要先了解该算法的核心,即裴蜀定理:

对任何整数(a,b),关于未知数x和y的线性丢番图方程(称为裴蜀等式):(ax+by=c),方程有整数解当且仅当(c)((a,b))的倍数。裴蜀等式有解时必然有无穷多个解。

证明

1.必要性证明:如果有整数解,则c是p的倍数(p=(a,b)),设(a=a"p)(b=b"p),则有((a",b")=1)成立。那么[ax+by=c\⇒a"px+b"py=c\⇒p(a"x+b"y)=c]那么(c)就是(p)的一个因数,所以(p|c)得证。

2.充分性证明:如果c是p的倍数,则ax+by=c有整数解(p=(a,b)),记欧几里得算法中每一次辗转得到的数对为((a_1,b_1),(a_2,b_2),...,(a_n,b_n)),其中,((a_1,b_1))即为((a,b))((a_n,b_n))即为((p,0)),符合辗转相除法的流程。对于((a_n,b_n)),求方程(a_nx+b_ny=c)的解,由于(a_n=p,b_n=0),我们可以构造一组解:[egin{cases}x_n=frac{c}{p}\∀y_nin Zend{cases}]适用于((a_n,b_n)),且((x_n,y_n))一定为整数(因为(p|c)(y_n)取任意整数)。

至此,数学归纳法的底基证明完毕。

由于辗转相除法,我们可以得知[a_n=b_{n-1} ①\b_n=a_{n-1}\%b_{n-1}\⇒b_n=a_{n-1}-lfloor a_{n-1}/b_{n-1}floor b_{n-1} ②]我们刚才已经推得:(a_nx+b_ny=c)的一组整数解((x_n,y_n)),那么可以把(①②)两式代入(a_nx+b_ny=c)得:[(b_{n-1})x+(a_{n-1}-lfloor a_{n-1}/b_{n-1}floor b_{n-1})y=c]且对于该方程,解((x_n,y_n))仍适用,即:[(b_{n-1})x_n+(a_{n-1}-lfloor a_{n-1}/b_{n-1}floor b_{n-1})y_n=c]成立,可以进行推导:[(b_{n-1})x_n+(a_{n-1}-lfloor a_{n-1}/b_{n-1}floor b_{n-1})y_n=c\⇒b_{n-1}x_n+a_{n-1}y_n-lfloor a_{n-1}/b_{n-1}floor b_{n-1} y_n=c\⇒a_{n-1}y_n+b_{n-1}(x_n-lfloor a_{n-1}/b_{n-1}floor y_n)=c ③]注意到两项的系数分别为(a_{n-1},b_{n-1}),所以对于方程(a_{n-1}x+b_{n-1}y=c),通过③式可以直接得到一组解:[egin{cases}x_{n-1}=y_n\y_{n-1}=x_n-lfloor a_{n-1}/b_{n-1}floor y_nend{cases}]由此,我们利用辗转相除法的关系,通过方程(a_nx+b_ny=c)的一组解((x_n,y_n)),推得了方程(a_{n-1}x+b_{n-1}y=c)的一组解((x_{n-1},y_{n-1}))同样地,我们可以由((x_i,y_i))的一组解,得到方程(a_{i-1}x+b_{i-1}y=c)的一组解((x_{i-1},y_{i-1}))[egin{cases}x_{i-1}=y_i\y_{i-1}=x_i-lfloor a_{i-1}/b_{i-1}floor y_iend{cases}]由上,数学归纳法完成证明:如果我们得知(a_nx+b_ny=c)的一组解((x_n,y_n)),且((a_1,b_1),(a_2,b_2),...,(a_n,b_n))是由辗转相除法得到的序列,那么我们就可以通过以上方法得到原方程(a_1x+b_1y=c)的解((x_1,y_1))

然而,我们已经通过构造法得到(a_nx+b_ny=c)的一组解((x_n,y_n)),且保证c是p的倍数时,整数解((x_n,y_n))一定存在。故c是p的倍数时,方程(ax+by=c)一定有整数解。充分性得证。

实现

回归正题,看扩展欧几里得算法。千万不要想着不看证明咯。裴蜀定理的充分性证明过程就是扩展欧几里得算法的流程。先由辗转相除法求解((a,b)),得到(p=(a,b))同时,构造解((x_n,y_n))[egin{cases}x_n=frac{c}{p}\∀y_nin Zend{cases}]在递归的回溯过程中,利用公式:[egin{cases}x_{i-1}=y_i\y_{i-1}=x_i-lfloor a_{i-1}/b_{i-1}floor y_iend{cases}]倒推每一组((a_i,b_i))的解((x_i,y_i))最后得到((a,b))和原方程(ax+by=c)的一组解((x,y))至此,扩展欧几里得算法完成。

(Code:)

#include<bits/stdc++.h>using namespace std;inline int Extended_Euclid(int a,int &x,int b,int &y,int c){ if(b==0){x=c/a,y=0;return a;} else { int p=Extended_Euclid(b,x,a%b,y,c); int x_=x,y_=y; x=y_; y=x_-a/b*y_; return p; }}int main(void){ int a,b,c; scanf("%d%d%d",&a,&b,&c); int p,x,y; p=Extended_Euclid(a,x,b,y,c); printf("(%d,%d)=%d",a,b,p); printf("x=%d,y=%d",x,y);}