『扩展欧几里得算法 Extended Euclid』

发布日期:2019-01-19


Euclid算法(gcd)

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

Extended Euclid算法(exgcd)

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

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

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

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

证明

1.必要性证明:如果有整数解则c是p的倍数(p=(ab)),设(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=(ab)),记欧几里得算法中每一次辗转得到的数对为((a_1b_1)(a_2b_2)...(a_nb_n)),其中,((a_1b_1))即为((ab))((a_nb_n))即为((p0)),符合辗转相除法的流程。对于((a_nb_n)),求方程(a_nx+b_ny=c)的解,由于(a_n=pb_n=0),我们可以构造一组解:[egin{cases}x_n=frac{c}{p}∀y_nin Zend{cases}]适用于((a_nb_n)),且((x_ny_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_ny_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_ny_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_ny_{n-1}=x_n-lfloor a_{n-1}/b_{n-1}floor y_nend{cases}]由此,我们利用辗转相除法的关系,通过方程(a_nx+b_ny=c)的一组解((x_ny_n)),推得了方程(a_{n-1}x+b_{n-1}y=c)的一组解((x_{n-1}y_{n-1}))同样地,我们可以由((x_iy_i))的一组解,得到方程(a_{i-1}x+b_{i-1}y=c)的一组解((x_{i-1}y_{i-1}))[egin{cases}x_{i-1}=y_iy_{i-1}=x_i-lfloor a_{i-1}/b_{i-1}floor y_iend{cases}]由上,数学归纳法完成证明:如果我们得知(a_nx+b_ny=c)的一组解((x_ny_n)),且((a_1b_1)(a_2b_2)...(a_nb_n))是由辗转相除法得到的序列,那么我们就可以通过以上方法得到原方程(a_1x+b_1y=c)的解((x_1y_1))

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

实现

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

(Code:)

#include<bits/stdc++.h>using namespace stdinline int Extended_Euclid(int aint &xint bint &yint c){ if(b==0){x=c/ay=0return a} else { int p=Extended_Euclid(bxa%byc) int x_=xy_=y x=y_ y=x_-a/b*y_ return p }}int main(void){ int abc scanf("%d%d%d"&a&b&c) int pxy p=Extended_Euclid(axbyc) printf("(%d%d)=%d"abp) printf("x=%dy=%d"xy)}