具体内容参见紫书p310-p312
一、辗转相除法
- 恒等式：gcd(a,b) = gcd(b,a%b)
- 边界条件：gcd(a,0) = a
辗转相除法的关键（恒等式）和边界条件一起构成了下面的程序：
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a%b);
}
这个算法称为欧几里得算法！！！！
二、求lcm
- 公式：gcd(a,b) * lcm(a,b) = a * b
正确的写法（先除后乘）：lcm(a,b) = a / gcd(a,b) * b