拓展欧几里得算法及代码实现

扩展欧几里得算法就是求：

　　　　　　ax + by = gcd(a, b)

的一组整数解(x, y)

一、非递归的实现：

首先看a = 60, b = 22的情况：

表格左边是欧几里得算法，右边等式计算ax + by = gcd(a, b)的解

这是《数论导引》里的伪代码：

1. 置x = 1, g = a, v = 0 与 w = b
2. 如果w = 0,则置y = (g - ax)/b，并返回值(g, x, y)
3. g除以w得余数t，g = qw + t
4. 置s = x - qv
5. 置(x, g) = (v, w)
6. 置(v, w) = (s, t)
7. 转到第2步

那么x是如何计算出来的呢，x是上上次余数的a的系数减去这次求得的q乘以上次余数的a的系数

也就是r(n) = r(n-2) - q(n)×r(n-1)　　　　(括号中的数代表下标)

这句话有点绕，=_=!!。。

再看一般情况的表格：

 1 int ex_gcd1(int a, int b, int &x, int &y)
 2 {
 3     int g, v, w, s, t, q;
 4     x = 1;
 5     v = 0;
 6     g = a;
 7     w = b;
 8     while(w != 0)
 9     {
10         q = g / w;
11         t = g % w;
12         s = x - q*v;
13         x = v;
14         g = w;
15         v = s;
16         w = t;
17     }
18     y = (g - a*x) / b;
19     return g;
20 }

代码君

二、递归方式的实现

令a‘ = a%b, t = a/b, y‘ = y + tx

ax + by = g

ax - tbx + tbx + by = g

(a - tb)x + b(tx + y) = g

a‘x + by‘ = g

by‘ + a‘x = g

y = y‘ - tx,y‘是比y深一度的递归的y

 1 int ex_gcd2(int a, int b, int &x, int &y)
 2 {
 3     if(b == 0)
 4     {
 5         x = 1;
 6         y = 0;
 7         return a;
 8     }
 9     int g = ex_gcd2(b, a%b, y, x);
10     y = y - a/b*x;
11     return g;
12 }

代码君

拓展欧几里得算法及代码实现,布布扣,bubuko.com

拓展欧几里得算法及代码实现

原文：http://www.cnblogs.com/AOQNRMGYXLMV/p/3856173.html