#Euclid Algorithm

* 용어 정의

G(최대공약수), L(최소공배수),

gcd(a, b) : a와 b의 최대공약수를 구해주는 함수

a = b * Q + r ( 0 <= r < b) 일때,

gcd(a, 0) = a,

gcd(a, b) = gcd(b, r) : 재귀적으로 적용됨

예) a = 8, b = 12

step1 : a = 8, b = 12

step2 : a = 12, b = 8 ( 8%12 )

step3 : a = 8, b = 4 ( 12%8 )

step4 : a = 4, b = 0 ( 8%4 )

* c_code recursion version

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

# 두 수와 최대공약수(G)와 최소공배수(L)

a = x*G, b = y*G, G = gcd(a, b) 이면 gcd(x, y) = 1이다.

L = x*y*G = a / gcd(a, b) * b,

(참고: L = a * b / gcd(a, b)는 결과가 overflow가 발생할 수 있으므로 비추천)

공약수 timer 1초 memory 64MB

공약수 1초 64MB