算法探秘：从辗转相除法到拓展欧几里得算法

辗转相除法又称欧几里得算法，是最常用的求两个正整数的最大公约数的算法，通常用于分数约分、判断两数是否互质等情况，在信息学奥赛大纲中也是难度系数3的数论知识。

但是在提高组的大纲要求中，还出现了难度系数为7的拓展欧几里得算法，这两者之间有何关系呢？加上了“拓展”二字，算法的难度有会出现什么样的变化呢？

辗转相除法（欧几里得算法）

★ 辗转相除法的基本原理是：两个整数的最大公约数（其缩写为gcd，在初赛题目中，可以根据这个缩写，立刻判断函数的功能可能是求最大公约数）等于较小的那个数与相除余数的最大公约数。因此不断循环这个过程，最后当余数为0时，当前算式的除数就是原两个整数的最大公约数。

例如：要求91和247的最大公约数，根据辗转相除法原理，可以这么做：

247÷91=2……65

91÷65=1……26

65÷26=2……13

26÷13=2……0

因此，13是91和247的最大公约数。

辗转相除法的代码实现

根据原理的描述，大家应该能容易想到使用递归算法来解决。

其中递推公式为：

gcd(m,n) = gcd(n,m%n)

边界条件为：

当m%n==0时，n就是原来两个数的最大公约数，return n即可。

代码展示：

int gcd(int m,int n){  if(m%n==0){    return n;  }  else{    return gcd(n,m%n);  }}

除了递归算法外，我们还可以使用迭代法，不断去更新需要做取模运算的两数，直到除数为0时结束循环，次数的被除数就是最大公约数。

（对应在案例中，需要再辗转一次，即13÷0，发现除数为0进行不了，那么13就是最大公约数）

代码展示：

int gcd(int m,int n){  while(n!=0){    int r=m%n; //计算余数     m=n; //新的被除数是上次的除数     n=r; //新的除数是上次的余数   }  return m;}

以上是两种辗转相除法，即欧几里得算法的代码实现方式。

先来解决倒水问题

在了解完欧几里得算法后，大家首先来思考一个经典问题：有一个能装a升水的无刻度容器，一个能装b升水的无刻度容器，如何用这两个容器量出c升的水？

我们先带入具体的数字试试看：用3升和5升的杯子a、b量出4升水。

大家有没有想出方法来呢？

先倒满3升的杯子a，再将水全都倒到杯子b中；

再倒满3升的杯子a，再用杯子a的水将杯子b倒满，此时杯子a中还剩1升水，杯子b满；

将杯子b倒空，将杯子a剩余的水倒进去，杯子b中有1升水；

最后一次倒满3升的杯子a，再将水全部倒入杯子b，这样杯子b中就获得了4升水。

将这个过程用一个数学表达式来表示：

a*3-b*1=4（其中a=3,b=5）

虽然水杯没有刻度，但是我们可以通过重复倒满整杯水或倒出整杯水的操作，想办法倒出想要的水量，抽象成数学模型就是：

对于表达式a*x+b*y=c（其中a,b,c已知且为整数），是否存在整数x,y，使等式成立。

法国数学家艾蒂安·裴蜀对这个问题给出了定理和证明。

裴蜀定理

如果a和b的最大公约数为c，即gcd(a,b) = c，那么一定存在一对整数x和y，使等式a*x+b*y=c成立。

其中有一个特别的定理：如果a、b两数互质，那么一定存在一对整数x、y，能让a*x+b*y=1成立。

根据这个定理，我们对倒水问题可以得出两个结论：

（1）如果a和b的最大公约数是c的整数倍，那么可以用a杯和b杯倒出c升水；

（2）如果a、b两数互质，那么我们可以用a、b这两个杯子倒出任意容量的水。

此外，还有一个与拓展欧几里得算法相关的结论：

若a*x+b*y=c（其中c为a和b的最大公约数），根据辗转相除法，b与a%b的最大公约数也是c，那么可以得到等式：

a*x+b*y=b*x1+(a%b)*y1

=b*x1+(a-a/b)*y1（注：这里和下面的a/b都是a整除b）

整理等式，可得：

a(x-y1)+b(y-(x1-(a/b)*y1)=0

为了让等式成立，当且仅当x=y1并且y=x1-(a/b)y1满足。

拓展欧几里得算法

那么，怎么求使a*x+b*y=c等式成立的一对整数x、y呢？这得和欧几里得算法结合起来。

我们知道辗转相除法的过程中会出现多对数字相除，这些数字就是求整数x、y的解的关键。

还是来举例说明吧。求让5*x+3*y=4等式成立的x与y，首先分析5和3辗转相除的过程：

5÷3=1……2

3÷2=1……1

2÷1=2……0

中间出现了(3,2)、(2,1)、(1,0)这三对数字，依次进行反向辗转相除：

（1）先求1*x+0*y=4的一组解，能容易求出x = 4，y = 0;

（2）再求2*x+1*y=4的一组解，根据上面裴蜀定理的分析，x=y1，因此可以让x=上一组的y=0，从而求得y=4；

（3）再求3*x+2*y=4的一组解，同样道理，x=上一组的y =4 ，从而求得y=-4；

（4）最后求5*x+3*y=4的一组解，x=上面的y = -4，求得y = 8;

（5）至此，能让5x+3y=4成立的一组解求出来了，即x=-4，y=8。

这里有同学可能会好奇，在案例中，我们通过模拟倒水，求出的x=-1，y=3，为什么用拓展欧几里得算法求得的是x=-4，y=8呢？

这是由于5和3是互质的，因此拓展欧几里得算法计算的是根据裴蜀定理5*x+3*y=1的解，然后再将答案扩大4倍的结果；

而x=-1,y=3只是我们根据具体情境凑出来的解，满足了裴蜀定理的公式，与拓展欧几里得算法没有关系。

拓展欧几里得算法

拓展欧几里得算法是通过递归算法来求满足a*x+b*y=gcd(a,b)等式的x与y。

递归的边界条件为：辗转相除到最后会出现求gcd(gcd(a,b),0)的式子，即gcd(a,b)÷0，此时对应的解为x=1,y=0;

递推公式为：

若已知b * x1 + (a%b) * y1 = gcd(a,b)的解，那么原式中

x = y1;

y =x1-(a/b)*y1（注：这里的a/b是a整除b）

因此，对应的代码为：

int exgcd(int a, int b, int &x, int &y){//返回值是a与b的最大公约数//x与y的答案需要用引用证明符来跟随递归变化   if(!b){ //边界条件    x=1, y=0;    return a;  }  int d=psgcd(b,a%b,y,x);   //递归完成后，此时x与y的值为x1与y1的值，但因为参数中x与y交换了位置，因此最终的x=y1已经实现，就差计算y的值了。  int x1=y, y1=x;  y=x1-(a/b)*y1;  return d;}