再说-扩展欧几里得算法

资料来源1：https://blog.csdn.net/

这个扩展是从原欧几里德算法扩展而来，这个算法真心非常有用！非常有用！非常有用！（中国剩余定理也要用到它）

首先说欧几里德算法(其实就是我们小时候数学课上就学过的辗转相除法求gcd)

欧几里德说：gcd(a,b) = gcd(b,a%b)

于是得到欧几里德算法：

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

该算法可以在几乎是log的时间算a,b的最大公因数gcd

PS:__gcd(a,b)库函数可以直接调用，但是有些OJ上提交会CE

现在，我们令a,b的最大公因数为gcd,那么我们一定可以找到一组x,y满足：（这个是欧几里德的定理一）

a*x + b*y = gcd;

此时，我们设x0,y0是上述不定方程的特解，那么就可以用x0,y0表示出整个不定方程的通解

x = x0 + (b/gcd)*t;
y = y0 - (a/gcd)*t;

然后是怎么求解通解x,y?

倒过去看看欧几里德算法，显然，它的结束条件是 b = 0的时候返回a

这就意味着，终止状态是 ：a = gcd ,b = 0;

将这组a,b代会不定方程ax+by=gcd,可以得到一组特解：x = 1,y = 0

找到终止状态，我们再看看递归的过程：

gcd = b*x1 + (a%b)*y1 
    = b*x1 + (a-(a/b)*b)*y1 // a%b = a-(a/b)*b
    = b*x1 + a*y1 - (a/b)*b*y1
    = a*y1 + b*(x1-a/b*y1)

最后得到gcd = a*y1 + b*(x1-a/b*y1)和原来的式子gcd = a*x + b*y一对比就得到:

x = y1,y = x1 - a/b*y1;

 

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

资料来源2：https://blog.csdn.net/

或者这样写，比较简洁，但是有点难理解，x和y交换那里。

 

//解方程ax+by=gcd(a,b) 返回gcd(a,b) 得到一组特解(x,y)
int extend_Euclid(int a, int b, int &x, int &y){
    if(b==0){
    x = 1; y = 0;
    return a;
    }
    int r = extend_Euclid(b, a%b, y, x);
    y -= a/b*x;
    return r;
}

拉梅定理：用欧几里得算法计算两个正整数的最大公因子时，所需的除法次数不会超过两个整数中较小的那个十进制数的位数的5倍。

推论：求两个正整数a,b,a>ba,b,a>b的最大公因子需要O(log2a)^3次的位运算。

扩展欧几里得的应用 
主要有：求解不定方程、模的逆元、同余方程。如POJ 1061，只要化为ax+by=cax+by=c的形式即可求解。

不懂之处：

是写错了吗？是不是就是上方的x = y1, y = x1 - a/b*y1呢？