최대공약수 및 확장 유클리드 알고리즘: ICPC 문제 풀이 및 개념 복습
최대공약수(GCD)의 원리
gcd(x, y)와 gcd(y, x % y)가 동일한 이유는 다음과 같습니다.
x와 y의 최대공약수를 d라고 가정합니다.
x = m * d, y = n * d라고 하면,
x % y = x - (x / y) * y가 됩니다.
이때 x / y는 정수 나눗셈 결과입니다.
x % y = m * d - (x / y) * n * d = (m - (x / y) * n) * d
따라서 x % y도 d의 배수입니다.
즉, x와 y의 공약수는 y와 x % y의 공 ...
7월 25일 04:37에 게시됨