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

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);}