gcd与lcm

最近做题又碰到了最大公约数（gcd）和最小公倍数（lcm），所以记录一下。

gcd和lcm有如下性质：

$ (m,n) (m,n) = m n$

我们知道gcd可以用辗转相除法求得，又因为有上述性质，lcm可以利用gcd来求得。以下是用C++写的实现代码。

int gcd(int x,int y){
    if(y==0) return x;
    return gcd(y,x%y); 
}
int lcm(int x,int y){ return x*y/gcd(x,y); }