GCD

輾轉相除得最大公約數。（也叫經典的歐幾里得算法）
a,b兩個數，小的那個假如a，另一個數就變小為b%a。
然後不斷遞歸下去，就能得到最大公約數gcd。
code：

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

時間複雜度logn，非常快。
下面解釋下原理：
1.首先a，b哪個先來被模不重要，輾轉一次就一定能得到小的那個了。
2.然後進行證明：
假設a=b*c+d
設a=kA，b=kB。
那麼d=a-bc,即d=Ak-Bkc,提個k，d=A-B*c。
這個時候d一定是整數，因為整數在[加，減，乘]的運算下是封閉的。
所以就模後的數就和除數，被除數有相同的公約數，就可以無限遞推下去了。

LCM

code：

int lcm(int a,int b){
    return a/gcd(a,b)*b;
}//就很簡單了。。。