算法研究之最大公約數

公約數：假設有兩個數a,b,所謂的公約數就是能把a,b整除的最大整數。

求最大公約數的方法有很多。

方法1：窮舉法，即通過循環找到一個2個數都能整除的數

方法2：歐幾裡德算法，公約數表示為f(a,b),并且有a>=b>0,歐幾裡德就給了我們一個很好的定理，f(a,b)=f(b,a%b)

我們來看下這個等式是怎麼來的

設有 r=a/b ,q=a%b

是以就有 a=a/b*b+q ----(這裡的a/b*b!=a ，原因就是我們用的是整數來計算的)

也就是a=r*b+q 變換一下有：q=a-r*b 設d=f(a,b)，a/d=m,b/d=n;則 有q=dm-r*dn=d(m-rn)

是以q/d也為0；設d|q表示d是q的約數；以下相同；

又有d|b;是以有d|(b,q),設D是(b,q)的最大公約數，則會有d<=D=f(b,q);

再回到前面r=a/b,q=a%b這兩個條件有

a=r*b+q,由于D|(b,q),是以D|a,是以有D|(a,b)

是以有D<=d=f(a,b),結合上部分就有d<=D <+d,及D=d;

是以得證；

通過遞歸的方法，我們很容易獲得這樣的算法：

方法3：對于大數來言，取模運算代價很大，是以我們可以利用f(x,y)=f(x-y,y)

這種方法和第二種方法相比，缺點在于遞歸疊代次數多。

方法3：

(1)如果y=k*y1,x=k*x1.那麼有f(x,y)=k*f(x1,y1)

(2)如果x=p*x2,p為素數，并且y%p != 0，那麼f(x,y) = f(p*x2,y) = f(x2,y)

于是我們得到下面的解決方法：

将p = 2,

若x，y均為偶數，f(x,y) = 2*f(x/2,y/2) = 2*f(x>>1,y>>1);

若x是偶數，y是奇數，f(x,y) = f(x/2,y) = f(x>>1,y);

若x是奇數，y是歐式，f(x,y) = f(x,y/2) = f(x,y>>1);

若x和y均為奇數，f(x,y) = f(y,x-y)。這時x-y一定是偶數，下一步一定會除以2。