首页 > 代码库 > 拓展欧几里得算法及代码实现
拓展欧几里得算法及代码实现
扩展欧几里得算法就是求：
ax + by = gcd(a, b)
的一组整数解(x, y)
一、非递归的实现：
首先看a = 60, b = 22的情况：
表格左边是欧几里得算法，右边等式计算ax + by = gcd(a, b)的解
| a = 2 × b + 16 | 16 = a - 2b |
| b = 1 × 16 + 6 | 6 = b - 1 × 16 = b - 1 × (a - 2b) = -a + 3b |
| 16 = 2 × 6 + 4 | 4 = 16 - 2 × 6 = (a - 2b) - 2 × (-a + 3b) 3a - 8b |
| 6 = 1 × 4 + 2 | 2 = 6 - 1 × 4 = (-a + 3b) - 1 × (3a - 8b) = -4a + 11b |
| 4 = 2 × 2 + 0 |
这是《数论导引》里的伪代码：
- 置x = 1, g = a, v = 0 与 w = b
- 如果w = 0,则置y = (g - ax)/b，并返回值(g, x, y)
- g除以w得余数t，g = qw + t
- 置s = x - qv
- 置(x, g) = (v, w)
- 置(v, w) = (s, t)
- 转到第2步
那么x是如何计算出来的呢，x是上上次余数的a的系数减去这次求得的q乘以上次余数的a的系数
也就是r(n) = r(n-2) - q(n)×r(n-1) (括号中的数代表下标)
这句话有点绕，=_=!!。。
再看一般情况的表格：
| a = q1b + r1 | r1 = a - q1b |
| b = q2r1 + r2 | r2 = b - q2r1 |
| r1 = q3r2 + r3 | r3 = r1 - q3r2 |
| …… | …… |
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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。