扩展欧几里得（exgcd(a,b)）

回顾

        由贝祖定理可知：ax+by=gcd(a,b)

        (a,y)为一组解

       （x+kb,y-ka）也为解

        所以有无数组解

一、扩展欧几里得算法

        x，y为整数，ax+by=gcd(a,b),求解一组x,y使得上式成立。

二、算法推导

        1.由欧几里得（辗转相除法）可知：

          2.递归边界为：b==0时，x=1,y=0

         推导：由欧几里得（辗转相除法）可知：

                    gcd(a,b)=gcd(b,a%b)

                    的边界条件时    r=0时

                   即gcd(a,0)=a

                   a*x1+0*y1=a

                   我们可以构造一组x1,y1

                   x1=1,y1可以为任意数

                   不妨  x1=1,y1=0

                   那么  x1=1,y1=0就是一组解。

         （由此依次往回返，令x=y1,y=x1-a/b*y1,就可以得到ax+by=gcd(a,b)的一组解（x,y）.）

        3.如果ax+by=c,c为gcd(a,b),c=p*gcd(a,b),我们如何找到整数解（x,y）使得ax+by=c成立呢？

        推导：假设ax1+by1=gcd(a,b)    式子1

                   由上可知：（x1,y1）的求解方法已知

                   始终可以找到（x1,y1）

                   让式子1两边乘p:apx1+bpy1=p*gcd(a,b)=c

                   所以：x=px1,y=py1(这样就找到了一组解）

                   其实求ax+by=c的解（x,y）

                   令p=c/gcd(a,b)

                   就是求：a/p*x+b/p*y=gcd(a,b)的整数解

三、求解步骤

1.求gcd(a,b)求解（x1,y1），ax1+by1=gcd（a,b）

2.求q=c/gcd(a,b)

3.x=qx1,y=qy1

(由贝祖定理可知，也可以推出无数组解）

四、算法实现

1.代码一：

#include<bits/stdc++.h>

using namespace std;

int exgcd(int a,int b,int &x,int &y)

{    int ret,tmp;

     if(b==0)

     {

        x=1;y=0;return a;}

        ret=exgcd(b,a%b,x,y);

        tmp=x;x=y;y=tmp-a/b*y;

        return ret;

      }

int  main()

{

         int a,b,x,y,z;

         scanf("%d%d",&a,&b);

         z=exgcd(a,b,x,y);

         printf("%d %d %dn",z,x,y);

         return 0;

}

思考：此时求出的整数解（x,y）并不能保证x为最小整数，若要保证x为最小整数怎么办？

综上可知，只要让：x=(x%b+b)%b，y=(z-a*x)/b

                               利用ax+by=1(ret=gcd(a,b))

                               y=(ret-ax)/b

2.代码二：

#include<bits/stdc++.h>

using namespace std;

int exgcd(int a,int b,int &x,int &y)

{    int ret,tmp;

     if(b==0)

     {

        x=1;y=0;return a;}

        ret=exgcd(b,a%b,x,y);

        tmp=x;x=y;y=tmp-a/b*y;

        return ret;

      }

int  main()

{

         int a,b,x,y,z;

         scanf("%d%d",&a,&b);

         z=exgcd(a,b,x,y);

         x=(x%b+b)%b；

         y=(z-a*x)/b；

         printf("%d %d %dn",z,x,y);

         return 0;

}