Lukémento Lukémento

알고있던 유클리드의 호제법이 생각이 나지 않아서 다시 한번 정리 해둔다.(열강 도전 프로그래밍 ONE을 보다가) 유클리드 호제법이란. A >= B인 어떤 두 정수 A와 B가 있을 때(A = Bq + r로 나타낼 수 있다.) A와 B의 최대공약수 gcd(A, B) = d는 gcd(B, r)과 같다. 즉, 쉽게 말하면 두 수의 최대공약수는 "큰 수를 작은 수로 나눈 나머지"와 "작은 수"의 최대공약수와 같다는 것이다. 증명. gcd(A, B) = d에 의해서 A = ad, B = bd (따라서 a와 b는 서로소이다.) A = Bq + r 이므로 r = A - Bq = ad - bdq = (a-bq)*d 이다. 여기서 B = bd 와 r = (a-bq)d이므로 d는 B와 r의 공약수 중 하나라는 것을 알 수 ..