정수론 - 확장 유클리드 호제법

 

유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것이다. 확장 유클리드 호제법을 제대로 이해하려면 수학 증명 과정까지 공부해야 하지만 여기서는 확장 유클리드 호제법 관련 문제를 풀기 위한 알고리즘만 설명한다.

 

 

확장 유클리드 호제법의 핵심 이론

확장 유클리드 호제법에서 해를 구하고자 하는 방정식은 다음과 같다.

 

해를 구하고자 하는 방정식
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이 되면 중단한다.

 

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

 

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

 

 

이해가 잘 안갔는데 이 글 보고 이해가 갔다.

https://wyv3rn.tistory.com/315

Expanded Euclid's Algorithm - 확장된 유클리드 호제법

 

 

---

 

[백준 21568번] Ax + By = C

https://www.acmicpc.net/problem/21568

 

확장 유클리드 호제법을 그대로 구현하면 되는 문제이다. 

 

1. C의 값이 A와 B의 최대 공약수의 배수 형태인지 확인한다. 최대 공약수의 배수 형태라면 C의 값 최대 공약수로 변경한다. 최대 공약수의 배수 형태가 아니라면 -1을 출력한 후 프로그램을 종료한다. 

 

 

2. A와 B에 관해 나머지가 0이 나올 때까지 유클리드 호제법을 수행한다. 

 

 

3. 나머지가 0이 나오면 x = 1, y = 0으로 설정한 후 과정 2에서 구한 몫들을 식 (x = y', y = x' - y' * 몫) 에 대입하면서 역순으로 계산한다.

 

4. 최종으로 계산된 x, y 값에 C를 x와 y의 최대 공약수로 나눈 값을 각각 곱해 방정식의 해를 구한다.

 

=> 5 / gcd(a, b) = 5

=> x = -1 * 5 = -5

=> y = 1 * 5 = 5

=> 정답은 (-5, 5)

 

 

[정답]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        if(C % gcd(A, B) != 0) {
            System.out.println(-1);
            return;
        }
        int K = C / (int) gcd(A, B);
        long[] ret = extended_gcd(A, B);
        System.out.println(ret[0] * K + " " + ret[1] * K);
    }
    public static long gcd(long a, long b) {
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    public static long[] extended_gcd(long a, long b) {
        long ret[] = new long[2];

        if(b == 0) {
            ret[0] = 1;
            ret[1] = 0;
            return ret;
        }

        long q = a / b;
        long[] v = extended_gcd(b, a % b);
        ret[0] = v[1];
        ret[1] = v[0] - v[1] * q;
        return ret;
    }
}

 

 

 

 

 

 

 

[참고 자료]

- do it! 알고리즘 코딩 테스트 자바편