欧几里德算法又称辗转相除法，用于求两个数的最大公约数。
其实我们需要知道的是一个公式：gcd(a,b) = gcd(b,a%b)
现在我们来举个例子模拟一下：求gcd(48,30)
步骤：
48 = 30 * 1 + 18
30 = 18 * 1 + 12
18 = 12 * 1 + 6
12 = 6 * 2 + 0
那么，gcd(48,30) = 6
我们可以写两种形式的辗转相除：递归和非递归。
递归的模板：
int gcd(int a,int b)
{
if(b==0)
return a;
return
gcd(b,a%b);
}
可以优化如下：
int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}
非递归的模板：
int Gcd(int a, int b)
{
while(b != 0)
{
int r = b;
b = a % b;
a = r;
}
return a;
}
然后求两个数的最小公倍数就是a*b/gcd(a,b);
0