????????歐幾里得算法用于求解兩個整數的最大公約數，又稱為輾轉相除

????????依據的基本定理：

????????????????GCD(a,b)=GCD(a%b,b)

證明：

????????對于搞理論的人可能需要會嚴格證明，但是對于我們一般人而言，只要能理解其原理并記住即可，后者實際上是非常簡單的，且看：

????????如果我們有兩個數a, b，假設其最大公約數m

????????那么有a%m==0，b%m==0

????????那么我們是不是可以將a看成k*b+c，那么(k*b+c)%m=(k*b)%m+c%m=0+c%m，容易發現m也正是b與c的最大公約數，

????????所以求a與b的最大公約數，也就是求c=a%b與b的最大公約數，于是基本定理就是這么來的：????????

• ? ? ? ????????? GCD(a,b)=GCD(a%b,b)

????????那么這樣輾轉相除下去，最后一定會得到0，

????????如果a是b的最大公約數m非1，那么得到(0,m)，最大公約數就是m

? ? ? ? 如果不是，那么最后a%b一定得1，即(1,b)，然后b%1==0，最后得（0，1），最大公約數就是1

????????這里需要注意參數順序, 要么:

????????????????GCD(a,b)=GCD(b,a%b)

????????????????GCD(a,b)=GCD(b%a,b)

? ? ? ? 不能寫成GCD(a,b)=GCD（a%b,b)，這樣會死遞歸

? ? ? ? 那么代碼就可以寫了：

int GCD(int a,int b)
{return a?GCD(b%a,a):b;
}

? ? ? ??