歐幾裡德算法

歐幾裡德是用來求最大公約數的，可以把它看成是狀态轉移，

對任意兩個數a，b（a>b），d=gcd（a，b），如果b不為零，那麼gcd（a，b）=gcd（b，a%b）

        證明： 令 r=a%b，即存在k，使得 a=b*k+r，那麼r=a-b*k；顯然r>=0,  r%d=（（a%d）-（b*k）%d）%d，因為a%d=b%d=0，是以r%d=0；

是以求gcd（a，b）可以轉移到求gcd（b，a%b），那麼這就是個遞歸過程了，那什麼時候遞歸結束呢，想一下，a，b不能為零，則可以把當b為零，作為遞歸的結束（當然還可以以其它結束條件），這就是求最大公約數的方法可以以其它結束條件），這就是求最大公約數的方法。

int gcd(int a,int b)
{
    if(b==0)return a;
 
    else return gcd(b,a%b);
 }