锐客网

  1. 首页 > it技术 > >

拓展欧几里得算法详解

算法导论

记得刚上初中的时候，数学课上老师讲过一种叫“二元一次不定方程”（形如ax + by = c （a≠0，b≠0，a、b、c为常数））的东西。当时，老师说：“二元一次不定方程有无数组解，对于任意实数x，都能找到一个y值使等式成立。”当时我们研究的范围是实数，如果说：当x，y以及a，b，c都是整数的时候，对于所有的整数x还都能找到一个整数y使得等式成立吗？

思考：ax + by = c
（a≠0，b≠0，a、b、c为常数）对于所有的整数x，是否都能找到一个整数y使得等式成立。（这个问题很简单，自己想一想吧！）
显然不能，就比如说x+2y=5当x=2时，y必须等于1.5等式才能成立，但是1.5不是整数。当数的范围被缩小到整数时，方程的解就可以被看成是直线“ax + by = c”穿过的“整数点”（横纵坐标都是整数的点），一般来说，解的个数还是无数个，就比如：2x+3y=1穿过(-1,1)，(2,-1)，(5,-3)，(8,-5)……但也有一些是无解的，就比如：2x+4y=1。
思考：二元一次不定方程在整数范围内有解的条件是什么？（一定要认真思考之后，再往下看。）
还是看刚刚我们说的那个式子：2x+4y=1。无论x、y是多少，2x+4y一定是偶数，而1却是奇数，一个奇数无论如何都不会与一个偶数相等。再比如：3x+6y=2，3x+6y一定是3的倍数，而2不是三的倍数，一个3的倍数不可能与一个不是3的倍数的数相等。因此：这个方程想要有解，c一定要是gcd(a, b)的倍数。
思考：如何用数学方法求出ax + by = c的一组整数解（原方程保证有解）。（这个问题有点难）
如果方程有解，那么c一定要是gcd(a, b)的倍数。不妨令gcd(a, b)=p，令c=np（n∈Z），原式为：ax + by = np即a (x/n) + b (y/n) = p。我们可以先去解这样一个方程：ax’+ by’=p，原方程的x就等于nx’，y就等于ny’。现在我们的当务之急就是解方程：ax + by = gcd(a, b)，这个问题比较不好想。
思考：如何解方程ax + by = gcd(a, b)。（提示：考虑辗转相除法的递归过程）
递归求解这个问题：辗转相除法告诉我们gcd(a, b)=gcd(b, a%b)，我们可以尝试从这个思路解决问题。假设我们已经知道了方程：bx+(a%b)y=gcd(b, a%b)=gcd(a, b)的解为(x0, y0)，如何去求方程ax + by =gcd(a, b)的解。尝试着把“模运算”展开，m%n=m-int(m/n)n （int表示取下整）。bx0 + (a – int (a/b)*b)*y0=gcd(a, b)，继续整理：y0*a +( x0-y0 int (a/b))b=gcd(a, b)。又因为ax + by = gcd(a, b)，所以：x=y0，y=x0-y0 int (a/b)。这样我们就可以递归下去求解了，退出条件是很显然的：当递归到gcd(a, b)*x+0*y=gcd(a, b)时，x=1 y=任意值，不妨令y=0（也可以令y等于其它值，这样会解出另外的一组的解，但也是成立的，从这个“y=任意值”，也可以分析出：该二元一次不定方程的整数解有无数组）。而这个求解ax + by = gcd(a, b)的过程就是所谓拓展欧几里得算法。
现在，试着写一下拓展欧几里得的代码吧！
struct PAIR//表示一个有序整数对(x,y) { int x,y; PAIR(int X=0,int Y=0)//初始化函数 { x=X; y=Y; } }; PAIR EXGCD(int a,int b)//求解ax+by=gcd(a,b) 返回(x,y) { if(b==0)//边界条件 return PAIR(1,0); PAIR LastAns=EXGCD(b,a%b); //递归求解 return PAIR(LastAns.y,LastAns.x-LastAns.y*int(a/b)); }

这就是拓展欧几里得算法的代码的主要部分，但是还有一些值得注意的细节。就比如这个EXGCD函数会默认a≥b，否则程序将无法正确运行，所以我们可以再写一个这样的函数：
PAIR exgcd(int a,int b) { if(a>=b)//a≥b直接计算 return EXGCD(a,b); else{ PAIR Ans=EXGCD(b,a); //交换一下 return PAIR(Ans.y,Ans.x); //这里也要反过来 } }

有了拓展欧几里得算法，我们就可以写一个求二元一次不定方程整数解的程序了，自己写写看吧！写完再看下面的样例代码。
int GCD(int a,int b) { if(b==0) return a; return GCD(b,a%b); } int gcd(int a,int b)//辗转相除法求最大公因数 { if(a

【拓展欧几里得算法详解】试着自己写一个求二元一次方程组整数解的程序吧！
赶稿匆忙，如有谬误，请谅解。
返回文章目录：Premier Bob的博客文章目录

    推荐阅读


    上一篇：Axon框架指南 - Baeldung

    下一篇：上直角三角形输出