문제 문제 바로가기 유클리드 호제법이란 정수 A와 B가 있다. A * s + B * t = r 을 만족하는 정수 s와 t가 있다는 것을 전제로 최대공약수 r을 구한다. 128과 42를 예시로 식을 풀어보자면, 128_s + 42_t = 최대공약수 r 128 = 42 * 어떤 몫 + r 형식으로 표현하고, 42와 r을 계속해서 풀어나가다 보면 나머지가 0이 된다. 그 때 마지막으로 대입됐던 수(이전 식의 나머지였던 수)가 128과 42의 최대 공약수가 된다. 128과 54 예시 128 = 54 * 2 + 20 54 = 20 * 2 + 14 20 = 14 * 1 + 6 14 = 6 * 2 + 2 6 = 2 * 3 + 0 따라서 2가 128과 54의 최대공약수이다. gcd는 최대공약수를 구할 때 사용한다. 파..
