最大公约数

辗转相除法

基于以下两条

  1. gcd(a, b) = gcd(b, a % b)
  2. gcd(a, 0) = a

有代码如下

  1. int gcd(a, b){
  2.     if(b == 0) return a;
  3.     else return gcd(b, a % b);
  4. }

最小公倍数

表示

  1. lcm(a, b) = a * b / gcd(a, b);
  2. lcm(a, b) = a / gcd(a, b) * b;

集合的思想

最大公约数是交集，最小公倍数是并集

数学的思想

最小公倍数可以将a, b都整除，那么lcm / a = b / gcd，同理lcm / b = a / gcd，都是符合条件的