Day-13 확장 유클리드 호제법

---

1. 확장 유클리드 호제법

• 확장 유클리드 호제법은 방정식의 해를 구하기 위해 사용된다.
• 해를 구하고자 하는 방정식은 ax + by = c 이다.
• 위 방정식은 c가 a, b의 최대 공약수의 배수인 경우에만 정수해를 가진다.
• 즉, c의 최솟값이 GCD(a, b)이다.

---

2. 확장 유클리드 호제법 구현

1. a와 b의 최대 공약수를 구해 c를 gcd로 둔다.
2. a, b로 유클리드 호제법을 반복 실행하며 몫과 나머지를 저장한다.
   나머지가 0이 될 때까지 반복한다.
3. 반복으로 구한 나머지와 몫을 이용하여 x = y', y = x' - y' * q를 계산한다.
   x', y'는 이전 x, 이전 y를 의미하고, q는 현재 보고 있는 몫을 의미한다.
   처음 시작하는 x, y는 x', y'를 1, 0으로 설정한다.
4. 구한 x, y에 c를 a와 b의 최대 공약수로 나눈 몫을 곱하여 해를 구한다.

---

3. 예제 문제

[21568] Ax+By=C (JAVA)

---

[14565] 역원(Inverse) 구하기 (JAVA)