Euclidean algorithm

update@2011-6-22
  今天在codeforces上遇到一个解二元一次方程的题 没思路,叽民哥说用欧几里德解,应该是个简单题但自己数学基础薄,只记住了GCD公式,今天得深究一下了。

欧几里德算法就是辗转相除法而且有很多相关的知识,下边一个一个说,它们之间有联系,但并不一定是因果关系。

1. gcd(a,b) 为a,b 的最大公约数,gcd(a,b) = gcd(b,a % b)
Q1.为什么是 gcd(b,a % b) 而不是gcd(a % b , b)
gcd(b,a%b)  gcd(a%b,b)
gcd(8,12)   gcd(8,12)
gcd(12,8)   gcd(8,12)
gcd(8,4)    gcd(8,12)

可以看得很清楚了gcd(b,a % b)可以保证:在大小顺序不符的时候 可以调换顺序;保留下较小值,用较大值去模较小值从而得到一个比较小值更小的值,而gcd(a%b,b) 最多只能工作一次


2. 关于最大公约数的性质:

例如,462可以分解成2 × 3 × 7 × 11;1071可以分解成3 × 3 × 7 × 17;最大公约数就等于 3 x 7 = 21 ; 那为什么不用分解质因数的方法呢,因为分解质因数要麻烦得多,尤其是当数很大的时候,很多加密算法之所以很难破解的原因就是分解质因数难;而辗转相除法的优点就是可以不必计算出所有质因数(有的地方叫素因数)的前提下求出最大公约数。这个性质其实很好得出,就拿上边的例子来说,g = 3x7 已经满足了倍数关系呢,但是不是最大的呢,当然是最大的,想要增大g  对于462来说可以乘以2 ,g = 2 x 3 x 7,现在用1071除以g得到 3 x 7 x 17 / 2 , 因为它们都是素数除了自己和1 其它的都不能整除的,你可能又有疑问了 3,7,17都不能被2整除,这没错,那它们的乘积呢,再看如下性质 :如果一个数w互素于数列a1、a2、…、an 中的每一个数,则w也一定互素于它们的乘积a1 × a2 × … × an,2 和 3,7,17 都是互素的,乘积也是互素,当然不能整除啦,这个性质我不会证明,所以打住吧。


3. 辗转相除法是基于如下原理:      下边是伪代码的形式

gcd(a ,b) = gcd(abs(a - b) , min(a,b))

        这个公式参数颠倒顺序无所谓 因为取的是绝对值

Q2.为什么不用这种方式求最大公约数?

当a b的差值很小时你会发现它也非常快,但是gcd(b , a%b) 更快

Q3.从 gcd(a ,b) = gcd(abs(a - b) , min(a,b)) 到 gcd(b , a%b)

假设 a >= b (在Q1 已经说明了我们总可以调换大小顺序的 保证左大右小)则
a = k*b + r (k = 1,2,3,...)这个应该很好想到(k 为商,r为余数)
gcd(abs(a - b) , min(a,b))的目的就是不断地用较大值减去较小值,一直减到不够减,即a=r的时候,与其不断地减减减 何不直接取余?!

Q4.a b c的最大公约数怎么算呢?

gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b).

写成一般的形式: gcd(a , b) = a*x + b*y  为了方便令gcd(a,b) = D

a*x + b*y = D;(1)

因为 gcd(a,b) = gcd(b, a % b) 辗转相除一次之后则有

b*(x ’ ) + (a % b)*(y ' ) = D---> b*(x ' ) + (a - a/b * b)*(y ' ) = D

再进一步整理为:a*(y ‘) + b*( (x ’ ) - a/b*(y ' ))= D  (2)

根据(1)(2) 可以得到 x = (y ' ) ; y = (x ’ ) - a/b*(y ' )

当b = 0时,a*x = gcd(a,0) = a, 得 x = 1. 这样我们就可以通过辗转相除求得x ,y的值,这就是扩展欧几里德 ,模板如下:



int Extened_Euclid(int a,int b,int &x,int &y){
    if(b == 0){
        x = 1; y = 0; return a;
    }
    else{
        int gcd,x1,y1;
        gcd = Extened_Euclid(b,a%b,x1,y1);
        x = y1; y = x1 - (a/b)*y1;
        return gcd;
    }
}