数论-欧几里得算法(辗转相除法)

1. 设  a = kb + r, 其中 a, b, q, r 都为整数, 那么:
           gcd(a, b) = gcd(b, r)
              

2. 设整数 a, b 且 b != 0. 做带余除法 a = qb + r, (0 <= r <= |b|). 
   若 r = 0, gcd(a, b) = b;
   若 r > 0, 在对b 于 r做带除余法 b = q'r + r'.
   若 r' = 0, gcd(a, b) = gcd(b, r) = r;
   重复上述过程, 直到余数为0;
              

3. 最大公约数  =  gcd(a, b);
   最小公倍数 = lcm(a, b) = (a * b)/gcd(a, b)
              

4. 代码实现:

int gcd(int a, int b)
    {
        return b == 0 ? a : gcd(b, a%b);
    }

    int lcm(int a, int b)
    {
        return (a * b)/gcd(a, b);
    }