欧几里得算法与扩展欧几里得算法（求二元一次不定方程、乘法逆元）

84 阅读 0 评论 56 点赞

我是靠谱客的博主传统大碗，最近开发中收集的这篇文章主要介绍欧几里得算法与扩展欧几里得算法（求二元一次不定方程、乘法逆元），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.欧几里得算法，即辗转相除法。用于求两个整数的最大公约数比较方便，时间复杂度为O（logN）N为两个整数的规模。
最大公约数，是能够同时被两个整数整除的最大整数。
比如说，求56和21的最大公约数：（每行数分别代表a=56,b=21,a%b）
56 21 14
21 14 7
14 7 0
7 0
此时得到最大公约数为7。
递归代码如下：

int gcd(int a, int b)
{
return b ? gcd(b, a%b) : a;
}

2.扩展欧几里得算法
顾名思义，扩展欧几里得算法就是对欧几里得算法的扩展，可以应用于求二元一次方程的通解、乘法逆元等。
对于上面的欧几里得算法，当递归到出口时，a=7,b=0。很容易就可以得到一组ax+by=7的解：x=1,y=0。
那么如何通过7x+y=7的解逆推出56x+21y=7的解呢？

	对于欧几里得算法的每一个状态，都存在ax+by=gcd(a,b)的解，我们假设有这样两组解（且他们为相邻状态）：
ax1+by1=gcd(a,b)
a'x2+b'y2=gcd(a',b')
那么可以知道：a'=b
b'=a%b
且gcd(a',b')=gcd(b,a%b)=gcd(a,b)，所以有
ax1+by1=bx2+(a%b)y2
另a%b可写为 a-a/b
所以有
ax1+by1=bx2+(a-(a/b)b)y2
故	ax1+by1=ay2+bx2+(a/b)by2
故	ax1=ay2
by1 = b(x2+ (a/b)by2)
故
x1=y2
y1 = x2 +(a/b)y2

故可以得到x1,y1与x2,y2的关系 : x1=y2 y1 = x2 +(a/b)y2
我们已知的是最后一组解，那么就要根据最后一组解逆推上去，就可以得到ax+by=gcd(a,b)的一组解了。
代码如下：

int exgcd(int a, int b, int&x, int &y)
{
if (!b)
{
x = 1;
y = 0;
return a;
}
int r = exgcd(b, a%b, x, y);
//递归到求出公约数，开始倒着求每一组的x,y。最后就得到这样一组特解了。
int t = x;
x = y;
y = t - (a / b)*y;
return r;
}

现在，通过扩展欧几里得算法，可以求出ax+by=gcd(a,b)的一组特解。那么如何求其通解呢？

3.二元一次方程通解
假设求得的特解为ax0+by0=r ,r=gcd(a,b).
ax0+by0+ab*k-ab*k=r
a(x0+b*k)+b(y0-a*k)=r
x=x0+b*k 、y=y0-a*k
这样写，可能不同组解的跨度太大了，所以可以写成
x=x0+(b/r)*k 、 y=y0-(a/r)*k

对于ax+by =c，而c不是a和b的最大公约数，其通解可以用 ax+by=gcd(a,b)的通解乘上 c/gcd(a,b)即可。

这里好像有一个贝祖定理：：对于给定的正整数a，b，方程ax+by=c有整数解的充要条件为c是gcd（a，b）的整数倍。

4.乘法逆元
另外，扩展欧几里得算法还可以用来求乘法逆元，首先看乘法逆元的定义：
如果ax≡1 (mod p),且gcd(a,p)=1（a与p互质），则称a关于模p的乘法逆元为x。通俗点讲就是 a*x的结果取余p为1。这样就可以转换成求ax+py=1的解。