확장 유클리드 호제법 자바 백준 BOJ 21568 Ax+By=C

확장 유클리드 호제법

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

제대로 이것을 이해하려면 수학적인 증명이 필요하지만 우리는 관련 알고리즘 구현만 알아봅시다.

 

확장 유클리드 호제법의 원리

해를 구하고자 하는 방정식은 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일 때 중지합니다.

 

유클리드 호제법 실행	나머지	몫
5 % 9 = 5	5	0
9 % 5 = 4	4	1
5 % 4 = 1	1	1
4 % 1 = 0	0	4

 

3. 반복으로 구한 나머지와 몫을 이용하여 거꾸로 올라가면서 x = y' , y' = x' - y' * q 을 계산합니다. 

여기서 x' 는 이전 x,  y' 는 이전 y, q 는 현재의 몫을 의미합니다.

처음 시작하는 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, 즉, K = 2 이며, 2 * 2, 2 * -1 에 의해 최초 방정식의 해는 4, -2 가 됩니다.

 

만약 ax + by = c 에서 c 가 gcd(a,b) 의 배수가 아니라면 어떻게 할까요?
오른쪽 변의 값이 gcd(A, B) 의 배수의 형태가 아니라면 결론부터 말하면  X, Y 값은 정수 범위에서 존재하지 않습니다. 
따라서 확장 유클리드 호제법을 구현할 때에는 먼저 c 가 gcd(a,b) 의 배수라는 조건을 만족하는 지를 먼저 판단해야 합니다.

 

백준 21568 Ax + By = C

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

21568번: Ax+By=C

 

1. 문제 분석

위에서 설명한 확장 유클리드 호제법을 그대로 구현하면 됩니다. 

2. 손으로 풀기

3.슈도코드

A: x의 계수, B: y의 계수, C: 우변 정수
// Ax + By = C
gcdVal: A 와 B 의 최대 공약수 저장
gcdVal = gcd(A, B)
K: 몇 배인지
quotientStack: 몫 스택

if(C 가 gcdVal 의 배수가 아니면) -> -1 출력,
else{
    K = 몇배인지 저장

    먼저 나머지가 0 일 때까지 유클리드 호제법 실행
    quotientGcd(A, B)

    tempX = 1, tempY = 0
    x = 0, y = 0
    while(스택이 빌 때까지){
        q = 스택.pop
        x = tempY
        y = tempX - (tempY * q)
        tempX = x;
        tempY = y;
    }
    K * x 와 K * y 출력.

}
// gcd func
quotientGcd(A, B){
    if(B == 0) -> return B;
    else -> gcd(B, A % B)
}
quotientGcd(A, B){
    quotientStack 스택에 A/B 몫을 추가.
    if(B == 0) -> return B;
    else {
        gcd(B, A % B)
    }
}

4. 코드

public class BaekJun21568 {

    static Stack<Long> quotientStack;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        long C = Long.parseLong(st.nextToken());
        long K;

        long gcdVal = gcd(A, B);
        if (C % gcdVal == 0) {
            K = C / gcdVal;
            quotientStack = new Stack<>();
            stackGcd(A, B);

            long tempX = 1;
            long tempY = 0;
            long x = 0;
            long y = 0;
            while (!quotientStack.isEmpty()) {
                long q = quotientStack.pop();
                x = tempY;
                y = tempX - (tempY * q);
                tempX = x;
                tempY = y;
            }
            System.out.println(K * x + " " + K * y);
        } else {
            System.out.println(-1);
        }
    }

    static long gcd(long A, long B) {
        if (B == 0) {
            return A;
        } else {
            return gcd(B, A % B);
        }
    }

    static long stackGcd(long A, long B) {
        while (B != 0) {
            long m = A % B;
            quotientStack.push(A / B);
            A = B;
            B = m;
        }
        if (B == 0) {
            return A;
        } else {
            return stackGcd(B, A % B);
        }
    }

}