最大公约数有结合律和交换律
gcd(a, b, c) == gcd(gcd(a, b), c) == gcd(a, gcd(b, c))
并且 gcd(a, b, c) == gcd(a, b - a, c - b)
这个有两种证明方法:
1.利用结合律
gcd(a, b, c) == gcd(gcd(a, b - a), gcd(b, c - b))
即分别算 a和b , b和c 的最大公约数
因为 b-a 和 b 在求最大公约数的角度上是相等的, 因为 b-a 中的所有的最大公约数 == b中的最大公约数
所以 gcd(b, c - b) => gcd(b - a, c - b)
因此 gcd(a, b, c) == gcd(a, b - a, c - b)
2.判断两个集合中的最大公约数恒相等 => a, b 的最大公约数 一定能够整除 a, b - a ....
最后: gcd(a, b) * lcm(a, b) = a * b
求最小公倍数时, 多添加一个1
不影响答案