유클리드호제법(최대공약수와 최소공배수) 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법이다. 호제법이라는 말은 '서로 나눈다'라는 뜻. 일반적으로 우리는 최대공약수를 구할 때 소인수분해를 하고 두 수의 공통인 소인수를 곱한다. 이 방법은 수가 커질수록 소인수분해하기 어려워진다는 단점이 있다. 이를 극복하기 위한 방법이 유클리드 호제법이다. 그렇다면, 유클리드 알고리즘을 어떻게 구현할 수 있을까? 바로 mod 연산(나머지 구하기 : %)을 반복하는 방법이다. why mod p? 답이 큰 정수인 경우, Overflow 에러를 막기 위해서 문제에서 큰 소수(보통 1,000,000,007)로 나눈 나머지를 요구 자연수 a, b에 대해 a를 b로 나눈 나머지는 r이다. (단 a>b) r에 대해, b를 ..