1、什么是GCD?GCD是最大公約數的簡稱(當然理解為我們偉大的黨也未嘗不可)。在開頭，我們先下幾個定義：a|b表示a能整除b(a是b的約數)amodb表示a-a/bb(a/b在Pascal中相當于adivb)gcd(a,b)表示a和b的最大公約數a和b的線性組合表示ax+by(x,y為整數)。我們有：若d|a且d|b，則d|ax+by(這很重要！)線性組合與GCD現在我們證明一個重要的定理：gcd(a,b)是a和b的最小的正線性組合。證明：設gcd(a,b)為d，a和b的最小的正線性組合為s*/d|a且d|b,d|so而amods=a-a/ss=a-a/s(ax+by)=a(1-a/sx)-ba

2、/sy亦為a和b的線性組合*.*amodss,amods不能是a和b的最小的正線性組合amods=0,即s|a同理由s|bs為a,b的公約數.s=dJd|sd=s。證畢。由這條定理易推知：若d|a且d|b,則d|gcd(a,b)Euclid算法現在的問題是如何快速的求gcd(a,b)。窮舉明顯不是一個好方法(0(n)，所以需要一個更好的方法。首先我們先提出一個定理：gcd(a,b)=gcd(b,a-bx)(x為正整數)。證明：設gcd(a,b)=d,gcd(b,a-bx)=e,貝IJd|a,d|b.d|a-bxd|gcd(b,a-bx)，即d|eJe|b,e|a-bxe|bx+(a-bx)，即

3、e|ae|gcd(a,b)，即卩e|dd=e。證畢。這個定理非常有用，因為它能快速地降低數據規模。當x=1時，gcd(a,b)=gcd(b,a-b)。這就是輾轉相減法。當x達到最大時，即x=a/b時，gcd(a,b)=gcd(b,amodb)。這個就是Euclid算法。它是不是Euclid提出的我不知道，但聽說是在Euclid時代形成的，所以就叫Euclid算法了。程序非常的簡單：functionEuclid(a,b:longint):longint;beginifb=0thenexit(a)elseexit(Euclid(b,amodb);end;Euclid算法比輾轉相減法好，不僅好在速度

4、快，而且用起來也方便。兩種算法都有一個隱含的限制：a=b。用輾轉相減法時，必須先判斷大小，而Euclid算法不然。若ab，則一次遞歸就會轉為gcd(b,a)，接著就能正常運行了。擴展Euclid前面我們說過，gcd(a,b)可以表示為a和b的最小的正線性組合。現在我們就要求這個最小的正線性組合ax+by中的x和y。這個可以利用我們的Euclid算法。從最簡單的情況開始。當b=0時，我們取x=1,y=0。當bD0時呢？假設gcd(a,b)=d，貝Igcd(b,amodb)=d。若我們已經求出了gcd(b,amodb)的線性組合表示bx+(amodb)y，貝Igcd(a,b)=d=bx+(amod

5、b)y=bx+(a-a/bb)y=ay+b(x-a/by)那么，x=y，y=x-a/by。這樣就可以在Euclid的遞歸過程中求出x和y。程序：functiongcd(a,b:longint):longint;varp,n,m:longint;beginifb=0thenbeginx:=1;y:=0;exit(a);endelsebeginp:=gcd(b,amodb);n:=x;m:=y;x:=m;y:=n-adivb*m;exit(p);end;end;我們現在還有一個問題：x,y是不是確定的？答案：不是。如果x,y符合要求，那么x+bk,y-ak也符合要求。不確定的原因在于這一句：“當b

6、=0時，我們取x=1,y=0。”實際上y可以取任何正整數。不定方程ax+by=c現在終于到了本文重點：解二元一次不定方程。看起來擴展Euclid算法是不定方程的一種特殊情況，實際上呢，不定方程卻是用Euclid算法解的。對于不定方程ax+by=c,設gcd(a,b)=d,如果ax+by=c有解，則d|c(這也是許多奧數題的切入點)。所以一旦d不是c的約數，那么ax+by=c一定無解。當d|c時，先求出ax+by=d=gcd(a,b)的x和y，貝Ix=x*c/d,y=y*c/d。由上一段可知，只要ax+by=c有一個解，它就有無數個解。Euclid算法還可以求解同余方程axDb(modm)。這其實和不定方程ax+my=b沒有區別。(不定方程和同余方程一般都有范圍限制，這其實也很容易解決，就