扩展欧几里德算法

原创

---

欧几里德算法是用来求最大公约数的：

1 int gcd(int a,int b)
2 {
3 　　return b==0?a:gcd(b,a%b);
4 }

扩展欧几里德算法描述为：已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。

扩展欧几里德常用在求解模线性方程及方程组中。（百度百科）

求解x，y的代码如下：

 1 int gcd(int a,int b)    //扩展欧几里德 
 2 {
 3     int d;
 4     if(b==0)
 5     {
 6         x=1;
 7         y=0;
 8         return a;
 9     }
10     else
11     {
12         d=gcd(b,a%b);
13         int temp;
14         temp=x;
15         x=y;
16         y=temp-(a/b)*y;
17         return d;
18     }
19 } 

已知 a*x+b*y==gcd(a，b)，gcd(a，b)==gcd(b，a%b)，将 gcd(b，a%b) 代入 a*x+b*y 可得 b*x1+(a%b)*y1==a*x+b*y（ 注意，(x，y) 和（x1,y1）是不同的 ，(x1，y1)是(x，y) 下层的递归值 ）

然后我们需要知道一个公式，a%b==a-（a/b）*b，将上式变形得 b*x1+（ a-(a/b)*b ）*y1==a*x+b*y，整理可得 a*y1+b*（x1-（a/b）*y）==a*x+b*y；

由此我们可知：

x==y1;

y==x1-（a/b）*y;

当递归到底层时，此时 b==0 ，从而能轻易的得出 gcd（a，b）==a，x==1，y==0；知道了最底层的（x，y），我们就可以根据公式递归回去求上面层的（x，y）。

此刻我们只求出了 a*x+b*y==gcd（a，b）的一组解，下面给出公式求剩下的解：

x=x0+a/gcd(a，b)*t；

y=y0-b/gcd(a，b)*t；　　

（x0，y0）为我们在上面求得的第一组解（x，y）；（t为任意整数，t==0时，就是我们上面的第一组解）

 1 #include<stdio.h>
 2 
 3 int x,y;
 4 
 5 int gcd(int a,int b)    //扩展欧几里德 
 6 {
 7     int d;
 8     if(b==0)    
 9     {
10         x=1;
11         y=0;
12         return a;
13     }
14     else
15     {
16         d=gcd(b,a%b);    //d存储最大公约数 
17         int temp;
18         temp=x;
19         x=y;
20         y=temp-(a/b)*y;
21         return d;
22     }
23 }
24 
25 int main()
26 {
27     int a,b;
28     scanf("%d%d",&a,&b);
29     int Byue=gcd(a,b);
30     printf("最大公约数为：%d\n",Byue);
31     printf("第一组解为：%d %d\n",x,y);
32     printf("有其余解如下：\n");     
33     int t;
34     for(t=1;t<=10;t++)    //另外给出10组解
35         printf("%d %d\n",x+b/Byue*t,y-a/Byue*t);
36 
37     return 0;
38 }

下面讨论二元一次方程 ax+by==c的解。

在 ax+by==gcd（a，b）（设解为x0，y0）的基础上等号两边同时乘以 c/gcd（a，b）就可以转换过来了。

所以方程的解为 ：

x=x0*（ c/gcd（a，b））；

y=y0*（ c/gcd（a，b））；

所以我们每求得一组 ax+by==gcd（a，b）的解，就能得到一组 ax+by==c 的解。

 1 #include<stdio.h>
 2 
 3 int x,y;
 4 
 5 int gcd(int a,int b)    //扩展欧几里德 
 6 {
 7     int d;
 8     if(b==0)    
 9     {
10         x=1;
11         y=0;
12         return a;
13     }
14     else
15     {
16         d=gcd(b,a%b);    //d存储最大公约数 
17         int temp;
18         temp=x;
19         x=y;
20         y=temp-(a/b)*y;
21         return d;
22     }
23 }
24 
25 int main()
26 {
27     int a,b,c;
28     printf("请输入 ax+by==c 中的 a,b,c: ");
29     scanf("%d%d%d",&a,&b,&c);
30     int Byue=gcd(a,b);
31     printf("最大公约数为：%d\n",Byue);
32     printf("第一组解为：%d %d\n",x*(c/Byue),y*(c/Byue));
33     printf("有其余解如下：\n");
34     int t;
35     for(t=1;t<=10;t++)    //另外给出10组解
36         printf("%d %d\n",( x+b/Byue*t )*(c/Byue),( y-a/Byue*t )*(c/Byue));
37 
38     return 0;
39 }

10:11:49

2018-04-19