扩展欧几里得算法(extgcd)

相信大家对欧几里得算法,即辗转相除法不陌生吧。

代码如下:

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

而扩展欧几里得算法,顾名思义就是对欧几里得算法的扩展。

切入正题:

首先我们来看一个问题:

求整数x, y使得ax + by = 1, 如果gcd(a, b) != 1, 我们很容易发现原方程是无解的。则方程ax + by = 1有正整数对解(x, y)的必要条件是gcd(a, b) = 1,即a, b 互质。

此时正整数对解(x, y)可以通过扩展欧几里得算法求得。

对于方程ax + by = gcd(a, b);我们设解为x1,  y1

我们令a = b, b = a % b;

得到方程bx + a % by = gcd(b, a % b);

由欧几里得算法可以得到gcd(a, b) = gcd(b, a % b);

代入可得:bx + a % b y = gcd(a, b)

设此方程解为x2, y2

在计算机中我们知道: a % b = a - (a / b) * b;

代入方程化解得:

ay2 + b(x2 - (a / b) y2) = gcd(a, b);

与ax1 + by= gcd(a, b) 联立,我们很容易得:

x1 = y2, y1 = x- (a / b)y2;

然后我们就这样可以解出来了。

等等我们似乎忘记一个东西了吧?对就是递归的终点。也就是最后方程的解x和y。

对于方程ay2 + b(x2 - (a / b) y2) = gcd(a, b);

当b = 0时,发现a * 1 + b * 0 = gcd(a, b)

则有x = 1, y = 0。

由此我们把ax + by = 1的其中一组解解出来了, 仅仅是其中一组解。

对于已经得到的解x1, y1;我们便可以求出通解。

我们设x = x1 + kt;t为整数

带入方程解得y = y1 - a * k / b * t;

而我们要保证y也为整数的话必须保证a * k /b也为整数,我们不妨令k = b/gcd(a, b);

所以通解为:

x = x1 + b / gcd(a, b) * t;

y = y1 -  a / gcd(a, b) * t;

其中t为整数。

附上伪代码:

int a, b, x, y;

int extgcd(int a, int b,int &x, int &y){
int d = a;
if(b != 0){
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}
else x = 1, y = 0;
return d;
}//d = gcd(a, b);

扩展欧几里得算法还可以用来解如下方程:

扩展欧几里得算法(extgcd)

ax = mt + b,ax - mt = b

这种形式不就是前面的形式吗?

上一篇:java发送短信--httpclient方式


下一篇:VC工程里,如何编译汇编语言的文件