• 유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것

핵심 이론

ax + by = c (a, b, c, x, y는 정수)

• 이때 위 방정식은 c % gcd(a, b) = 0인 경우에만 정수해를 가짐
  • 다시 말해 c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가짐
  • 이는 ax + by = c가 정수해를 갖게 하는 c의 최솟값이 gcd(a, b)라는 것을 의미
• 구현에는 재귀 함수 사용

5x + 9y = 2일 때 이 식을 만족하는 정수 x, y 값을 구해 보자.

1. 우선 5x + 9y가 정수해를 갖게 하는 c의 최솟값이 gcd(5, 9)라는 것을 적용하여 식을 다시 놓는다. gcd(5, 9) = 1이므로 5x + 9y = 1로 식을 다시 놓고 다음 단계를 진행한다.
2. a, b로 유클리드 호제법을 반복 실행하며 몫, 나머지를 저장한다. 반복은 나머지가 0이 되면 중단한다.

1. 반복으로 구한 나머지와 몫을 이용하여 거꾸로 올라가며 x = y’, y = x’ - y’ * q를 계산한다. x’는 이전 x, y’는 이전 y를 의미하고, q는 현재 보고 있는 몫을 의미한다. 이때 처음 시작하는 x, y는 이전 x와 이전 y가 없으므로 각각 1, 0으로 지정하여 역계산을 진행한다.(밑에서 위로 진행)

1. 이렇게 재귀 방식으로 알아낸 최종 x, y는 ax + by = gcd(a, b)를 만족한다. 그리고 c / gcd(a, b) = K를 가정하면 최초 방정식의 해는 Kx, Ky로 간단히 구할 수 있다. 과정 3에서 찾은 x는 2, y는 -1이고 K값을 구하면 2(c값) / 1(최대 공약수) = 2가 되므로 2의 값을 기존의 x(2), y(-1) 값에 각각 곱한다. 이에 따라 최초 방정식의 해는 4, -2가 된다.

[045] Ax + By = C

• https://www.acmicpc.net/problem/21568
• c % gcd(a, b) == 0 만족하지 않으면 -1 출력
• K = c / gcd(a, b)
• 이론 유클리드 호제법과 역순 실행하여 x, y 값 구함