原创

---

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

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     else11     {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
     
       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     else15     {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
     
       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     else15     {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