拓展欧几里得

引用博客：http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

对于普通的GCD,也就是求两个数的最大公约数

对于拓展GCD，也就是拓展欧几里得算法

定义：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

证明：设 a>b。

　　1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；

　　2，ab!=0 时

　　设 ax1+by1=gcd(a,b);

　　bx2+(a mod b)y2=gcd(b,a mod b);

　　根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);

　　则:ax1+by1=bx2+(a mod b)y2;

　　即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;

　　根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;

     这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

　  上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

那么当 ax+by = c的时候呢

要看这个有没有整数解，那么可以判断c%gcd(a,b)是否等于0,也就是说判断一下c是不是gcd(a,b)的倍数，如果是倍数的话，由于上面的证明，可知可以找到到解

假设 解为 x0，y0

那么通解就是 x = x0+b/gcd(a,b)*t    y  =y0-a/gcd(a,b)*t；

其中t是整数，为什么通解会是这样呢

带入原式  ax0+a*b/gcd(a,b)*t+by0-a*b/gcd(a,b)*t = c

很明显可以 得到 ax0+by0 = c，其中x0,y0也就是已找到的解，那么这个通式很明显成立，至于为什么是/gcd而不是直接a,b，那是因为a/gcd(a,b)的解肯定是a的因子，然后就可以获得更多的解

就是说 a/gcd(a,b)*t 的解要笔a*t 的解要多很多，也就是 a*t∈a/gcd(a,b)*t

递归的代码

//拓展gcd

int ex_gcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int r = ex_gcd(b,a%b,x,y);
    int tmp = x;
    x = y;
    y = t-a/b*y;
    return r;
}

 

返回值就是最小的公约数