文档介绍：什么是GCD?
GCD是最大公约数的简称(当然理解为我们伟大的党也未尝不可)。在开头,我们先下几个定义:
①a|b表示a能整除b(a是b的约数)
②a mod b表示a-[a/b]b([a/b]在Pascal中相当于a div b)
③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|s。
而a mod s=a-[a/s]s
         =a-[a/s](ax+by)
         =a(1-[a/s]x)-b[a/s]y
亦为a和b的线性组合
∵a mod s<s,a mod s不能是a和b的最小的正线性组合
∴a mod s=0,即s|a
同理由s|b
∴s为a,b的公约数
∴s<=d
∵d|s
∴d=s。证毕。
由这条定理易推知:若d|a且d|b,则d|gcd(a,b)
Euclid算法
现在的问题是如何快速的求gcd(a,b)。穷举明显不是一个好方法(O(n)),所以需要一个更好的方法。
首先我们先提出一个定理:gcd(a,b)=gcd(b,a-bx)(x为正整数)。
证明:
设gcd(a,b)=d,gcd(b,a-bx)=e,则
∵d|a,d|b
∴d|(a-bx)
∴d|gcd(b,a-bx),即d|e
∵e|b,e|a-bx
∴e|[bx+(a-bx)],即e|a
∴e|gcd(a,b),即e|d
∴d=e。证毕。
这个定理非常有用,因为它能快速地降低数据规模。
当x=1时,gcd(a,b)=gcd(b,a-b)。这就是辗转相减法。
当x达到最大时,即x=[a/b]时,gcd(a,b)=gcd(b,a mod b)。这个就是Euclid(欧几里德)算法。
它是不是Euclid提出的我不知道,但听说是在Euclid时代形成的,所以就叫Euclid算法了。
程序非常的简单:
function Euclid(a,b:longint):longint;
 begin
  if b=0 then exit(a)
         else exit(Euclid(b,a mod b));
 end;
Euclid算法比辗转相减法好,不仅好在速度快,而且用起来也方便。两种算法都有一个隐含的限制:a>=b。用辗转相减法时,必须先判断大小,而Euclid算法不然。若a<b,则一次递归就会转为gcd(b,a),接着就能正常运行了。
扩展Euclid
前面我们说过,gcd(a,b)可以表示为a和b的最小的正线性组合。现在我们就要求这个最小的正线性组合ax+by中的x和y。这个可以利用我们的Euclid算法。
从最简单的情况开始。当b=0时,我们取x=1,y=0。当b≠0时呢?
假设gcd(a,b)=d,则gcd(b,a mod b)=d。若我们已经求出了gcd(b,a mod b)的线性组合表示bx'+(a mod b)y',则
gcd(a,b)=d
        =b