數論初步-歐幾裡得算法，數論-歐幾裡得算法

數論初步-歐幾裡得算法，數論-歐幾裡得算法

1 int judge(int* X) {
2 X[2] /= gcd(X[2], X[1]);
3 for(int i = 3; i <= k; i++) X[2] /= gcd(X[i], X[2]);
4 return X[2] == 1;
5 }

這個算法稱為歐幾裡得算法。不會溢出，因為gcd函數的遞歸層數不超過4.785lgN + 1.6723，其中N=max{a,b}。 讓gcd遞歸層數最多的是gcd(Fn,Fn-1)。利用gcd還可以求出兩個整數a和b的最小公倍數lcm(a,b)。 這個結論很容易由唯一分解定
理得到。由此不難驗證gcd(a,b)*lcm(a,b)=a*b。

不過即使有了公式也不要大意。 如果把lcm寫成a *b/gcd(a,b)，可能會因此丟掉不少分數——a*b可能會溢出！正確的寫法是先除後乘，即a/gcd(a,b) * b。 這樣一來，只要題面上保證最終結果在int范圍之內，這個函數就不會出錯。
但前一份代碼卻不是這樣：即使最終答案在int范圍之內，也有可能中間過程越界。 注意這樣
的細節，畢竟算法競賽不是數學競賽。