歐幾里德算法

歐幾里德算法又稱輾轉(zhuǎn)相除法，用于計(jì)算兩個(gè)整數(shù)a,b的最大公約數(shù)。其計(jì)算原理依賴于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

證明：a可以表示成a = kb + r，則r = a mod b

假設(shè)d是a,b的一個(gè)公約數(shù)，則有

d|a, d|b，而r = a - kb，因此d|r

因此d是(b,a mod b)的公約數(shù)

假設(shè)d 是(b,a mod b)的公約數(shù)，則

d | b , d |r ，但是a = kb +r

因此d也是(a,b)的公約數(shù)

因此(a,b)和(b,a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證

歐幾里德算法就是根據(jù)這個(gè)原理來(lái)做的，其算法用C++語(yǔ)言描述為：

int Gcd(int a, int b)

{

    if(b == 0)

        return a;

    return Gcd(b, a % b);

}

int Gcd(int a, int b)

{

    while(b != 0)

    {

        int r = b;

        b = a % b;

        a = r;

    }

    return a;

}

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

{

    if(b == 0)

    {

        x = 1;

        y = 0;

        return a;

    }

    int r = exGcd(b, a % b, x, y);

    int t = x;

    x = y;

    y = t - a / b * y;



    return r;

}

有了上述規(guī)律就可以給出Stein算法如下：

如果A=0，B是最大公約數(shù)，算法結(jié)束

如果B=0，A是最大公約數(shù)，算法結(jié)束

設(shè)置A1 = A、B1=B和C1 = 1

如果An和Bn都是偶數(shù)，則An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(注意，乘2只要把整數(shù)左移一位即可，除2只要把整數(shù)右移一位即可)

如果An是偶數(shù)，Bn不是偶數(shù)，則An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (很顯然啦，2不是奇數(shù)的約數(shù))

如果Bn是偶數(shù)，An不是偶數(shù)，則Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (很顯然啦，2不是奇數(shù)的約數(shù))

如果An和Bn都不是偶數(shù)，則An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn

n++，轉(zhuǎn)4

這個(gè)算法的原理很顯然，所以就不再證明了?，F(xiàn)在考察一下該算法和歐幾里德方法效率上的差別。

給出一個(gè)C++的實(shí)現(xiàn):

int Gcd(int a, int b)

{

    if(a == 0) return b;

    if(b == 0) return a;

    if(a % 2 == 0 && b % 2 == 0) return 2 * gcd(a >> 1, b >> 1);

    else if(a % 2 == 0)  return gcd(a >> 1, b);

    else if(b % 2 == 0) return gcd(a, b >> 1);

    else return gcd(abs(a - b), Min(a, b));

}

考慮歐幾里德算法，最惡劣的情況是，每次迭代a = 2b -1,這樣，迭代后，r= b-1。如果a小于2N，這樣大約需要 4N次迭代。而考慮Stein算法，每次迭代后，顯然AN+1BN+1≤ ANBN/2，最大迭代次數(shù)也不超過(guò)4N次。也就是說(shuō)，迭代次數(shù)幾乎是相等的。但是，需要注意的是，對(duì)于大素?cái)?shù)，試商法將使每次迭代都更復(fù)雜，因此對(duì)于大素?cái)?shù)Stein將更有優(yōu)勢(shì)



練習(xí):

OJ上面的赤裸裸的Gcd算法的題不多，大多都是套了一個(gè)外殼。

找了兩道，可以試試看

HDOJ 2028 Lowest Common Multiple Plus   這個(gè)是求n個(gè)數(shù)的最小公倍數(shù)(有了最大公約數(shù)，最小公倍數(shù)應(yīng)該很容易了）

ZJU 2678 Bishops on a Toral Board  這個(gè)題目要發(fā)現(xiàn)規(guī)律，不錯(cuò)的題目