扩展欧几里得算法

简介:   问题:ax+by=c,已知a、b、c,求解使该等式成立的一组x,y。其中a、b、c、x、y均为整数 a,b的最大公约数为gcd(a,b)。如果c不是gcd(a,b)的倍数,则该等式无解,因为等式左边除以gcd(a,b)是整数,而等式右边除以gcd(a,b)后为小数。

  问题:ax+by=c,已知a、b、c,求解使该等式成立的一组x,y。其中a、b、c、x、y均为整数 a,b的最大公约数为gcd(a,b)。如果c不是gcd(a,b)的倍数,则该等式无解,因为等式左边除以gcd(a,b)是整数,而等式右边除以gcd(a,b)后为小数。因此,只有当c是gcd(a,b)的倍数的时候,该等式有解。这样,可以通过计算使ax1+by1=gcd(a,b)成立的x1、y1,然后有x=(c/gcd(a,b))*x1,y=(c/gcd(a,b))*y1,得到x,y。 问题就被转换为求使ax+by=gcd(a,b)成立的一组x,y。  

  如果b不为零,根据欧几里德定理,可以设 ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2=bx2+(a-(a/b)*b)y2 化简后有x1=y2,y1=x2-(a/b)y2。因此x1,y1依赖于x2,y2,同理依次类推递归调用求出x3,y3,x4,y4……,类似于辗转相除,直到b=0时,求出xn,yn,便可以推出x1,y1的值。

  

 1 // 返回a,b的最大公约数
 2 int extended_euclid(int a, int b, int &x, int &y)
 3 {
 4     if(b == 0) // gcd(a, b) == a
 5      {
 6          x = 1;
 7          y = 0;
 8         return a;
 9      }
10     int n = extended_euclid(b, a%b, x, y);
11     int tmp = x;
12      x = y;
13      y = tmp - static_cast<int>(a/b)*y;
14     return n;
15 }

   其它解为x0 + k*b/gcd(a,b),y0-k*a/gcd(a,b),具体参考白书P179.

目录
相关文章
|
2月前
|
算法
class072 最长递增子序列问题与扩展【算法】
class072 最长递增子序列问题与扩展【算法】
30 0
|
2月前
|
算法
class071 子数组最大累加和问题与扩展-下【算法】
class071 子数组最大累加和问题与扩展-下【算法】
32 0
|
2月前
|
算法 数据处理 C++
【C++ 20 新特性 算法和迭代器库的扩展和泛化 Ranges】深入浅出C++ Ranges库 (Exploring the C++ Ranges Library)
【C++ 20 新特性 算法和迭代器库的扩展和泛化 Ranges】深入浅出C++ Ranges库 (Exploring the C++ Ranges Library)
329 1
|
1月前
|
机器学习/深度学习 算法 搜索推荐
【初阶算法4】——归并排序的详解,及其归并排序的扩展
【初阶算法4】——归并排序的详解,及其归并排序的扩展
【初阶算法4】——归并排序的详解,及其归并排序的扩展
|
2月前
|
算法 数据安全/隐私保护
什么是扩展欧几里得算法?
【5月更文挑战第13天】什么是扩展欧几里得算法?
44 3
|
2月前
|
算法 Python
Python欧几里得算法找最大公约数
Python欧几里得算法找最大公约数
23 0
|
2月前
|
算法 搜索推荐 程序员
C语言第三十三练—— KMP算法和扩展 KMP算法
C语言第三十三练—— KMP算法和扩展 KMP算法
48 0
|
2月前
|
算法 搜索推荐 程序员
C语言第二十二练——扩展欧几里得算法
C语言第二十二练——扩展欧几里得算法
38 0
|
2月前
|
算法
class070 子数组最大累加和问题与扩展-上【算法】
class070 子数组最大累加和问题与扩展-上【算法】
27 0
|
2月前
|
算法 测试技术
class062 宽度优先遍历及其扩展【算法】
class062 宽度优先遍历及其扩展【算法】
33 0

热门文章

最新文章