欧几里得+扩展的欧几里得算法+线性同余方程+中国剩余定理

http://www.nowamagic.net/academy/detail/40110119
欧几里得算法：

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数

view source

print?

1	gcd(a, b) = gcd(b, a mod b)

扩展欧几里德算法

由朴素欧几里得算法我们可以得出扩展欧几里德算法：对于不全为 0 的非负整数 a、b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

就是给两个整数 a,b 必然存在一对整数 x,y 使得 ax + by = gcd(a,b)，这个定理又叫贝祖定理。

void gcdEx(const int a,const int b,int& x,int& y){

    if (b){

//      gcdEx(b,a % b,x,y);

//      int t = x;

//      x = y;

//      y = t - (int)(a / b) * y;

        // 上面四句可化简为下面两句

        gcdEx(b,a % b,y,x);

        y -= (int)(a / b) * x;

    } else {

        x = 1;

        y = 0;

    }

}

http://www.nowamagic.net/academy/detail/40110122

已知等式 47x + 30y = 1; 求x,y的整数解。

设扩展欧几里德算法为gcdEx(a,b,x,y) 其中a,b为已知,x,y为所求。那么gcdEx(a,b,x,y)函数就有如下的计算过程：

解释一下这个过程：

1. 左边是利用朴素欧几里德算法相除得到一系列中间值，gcdEx(47,30,x,y)，a = 47，b = 30，所以 gcd(47, 30) = gcd(b, a%b) = gcd(30, 17)，直到b=0。

2. 当b=0时，可以得知x=1，y=0，当知道这两个值的时候，就可以开始根据扩展欧几里德算法倒推了。还记得那个定理吗？这里再说一次：

1

x1 = y2

2	y1 = x2 - (int)(a/b) * y2

3. 往上一步的x,y看作x1,y1，下面“旧”的x,y看作x2,y2，利用朴素欧几里德算法推导出的结论,x1=y2,y1=x2-(a/b)*y2。其中a,b就是当前gcdEx中的a,b.当这样递归回去到了第一个调用点时,所得到的x,y就是结果,即x=-7,y=11;

扩展欧几里得算法就是不断地的将b放小，直至b等于0，最后反推求回x和y。前面不断的递归求解一定会有个时候 b=0，所以递归可以结束。结束之后再利用定理反推。

http://www.nowamagic.net/academy/detail/40110128
小珂是一名初中生，她现在很苦恼，因为老师布置了一个让她苦恼的作业，你能不能帮助她呢？题目信息如下：
已知二元一次方程 a*x+b*y=n，判断这个二元一次方程有没有整数解，x、y为未知数，其中a、b、n都为整数且不等于零，同时满足0 < a,b,n < 2^16-1。

根据扩展欧几里德算法我们知道，对于与不完全为 0 的非负整数 a 和 b，gcd(a,b)表示 a 和 b 的最大公约数，那么存在唯一的整数 x、y，使得 gcd(a,b)=ax+by。

那么问题现在就简单了，就是比较 gcd(a,b) 与 n，如果他们模为0，那么就 a*x+b*y=n 就有解，否则无解。

http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

扩展欧几里德算法的应用主要有以下三方面：

（1）求解不定方程；

（2）求解模线性方程（线性同余方程）；

（3）求解模的逆元；