[21568] Ax+By=C

✔ Ax+By=C

[백준 21568]

문제 분석하기

확장 유클리드 호제법을 그대로 구현

손으로 풀어보기

1. C의 값이 A와 B의 최대 공약수의 배수 형태인지 확인한 후, 최대 공약수의 배수 형태라면 C의 값을 최대 공약수로 변경
   • 최대 공약수의 배수 형태가 아니라면 -1을 출력한 후 프로그램을 종료
2. A와 B에 관해 나머지가 0이 나올 때까지 유클리드 호제법을 수행
3. 나머지가 0이 나오면 x = 1, y = 0으로 설정한 후 미리 구한 몫들의 식에 대입하면서 역순으로 계산
4. 최종으로 계산된 x, y 값에 C를 x와 y의 최대 공약수로 나눈 값을 각각 곱해 방정식의 해를 구함

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

1. 5x + 9y = 2 → 5x + 9y = 1

2. 유클리드 호제법을 반복 실행하며 몫, 나머지를 저장

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

3. 반복으로 구한 나머지와 몫을 이용하여 거꾸루 올라가며 계산

나머지	몫	x = y', y = x' - y' + q 역순 계산
0	4	x = 0, y = 1 - 0 * 4 = 1
1	1	x = 1, y = 0 - 1 * 1 = -1
4	1	x = -1, y = 1 - (-1 * 1) = 2
5	0	x = 2, y = -1 - (2 * 0) = -1

4. 재귀 방식으로 알아낸 최종 x, y를 구하고 최초 방정식이 해를 구함

x는 2, y는 -1이므로 2 / 1 = 2이며, 2 * 2, 2 * -1에 의해 최초 방정식의 해는 4, -2

슈도코드 작성하기

a(1번째 수) b(2번째 수) c(3번째 수)
최대 공약수 = gcd(a, b)
if(c가 최대 공약수의 배수가 아니라면) -1 출력하기
else {
    나머지(b)가 0이 될 때까지 재귀 함수를 호출하는 유클리드 호제법 함수 호출하기
    결괏값에 c/최대 공약수의 값을 곱한 후 해당 값을 출력하기
}
Excute(a, b) {
    if(b == 0) 재귀 함수를 중단하고 return
    Exceute(b, a % b)
    x = y', y = x' - y' * 몫을 계산하는 연산 로직 구현하기
}

gcd {
    if(b가 0이면) a가 최대 공약수
    else {
        gcd(작은 수, 큰 수 % 작은 수)
    }
}

코드 구현하기

/**
 * 21568) Ax+By=C
 */
public class D045_21568 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // a(1번째 수)
        int a = Integer.parseInt(st.nextToken());
        // b(2번째 수)
        int b = Integer.parseInt(st.nextToken());
        // c(3번째 수)
        int c = Integer.parseInt(st.nextToken());
        // a와 b의 최대 공약수
        long gcd = gcd(a, b);
        // c가 최대 공약수의 배수가 아니라면
        if (c % gcd != 0) {
            // -1 출력하기
            System.out.println(-1);
        } else {
            int mok = (int) (c / gcd);
            // 나머지(b)가 0이 될 때까지 재귀 함수를 호출하는 유클리드 호제법 함수 호출하기
            long[] ret = Excute(a, b);
            // 결괏값에 c/최대 공약수의 값을 곱한 후 해당 값을 출력하기
            System.out.println(ret[0] * mok + " " + ret[1] * mok);
        }
    }

    public static long[] Excute(long a, long b) {
        long[] ret = new long[2];
        // if(b == 0) 재귀 함수를 중단하고 return
        if (b == 0) {
            ret[0] = 1;
            ret[1] = 0;
            return ret;
        }
        // 현재 보고 있는 몫
        long q = a / b;
        // 재귀를 빠져나오는 영역에서 자연스럽게 역순이 저장됨
        long[] v = Excute(b, a % b);
        // x = y' 계산
        ret[0] = v[1];
        // y = x' - y' * 몫 계산
        ret[1] = v[0] - v[1] * q;
        return ret;
    }

    // 최대 공약수 함수 구현하기
    public static int gcd(int a, int b) {
        // if(b가 0이면)
        if (b == 0)
            // a가 최대 공약수
            return a;
        else
            // gcd(작은 수, 큰 수 % 작은 수)
            return gcd(b, a % b);
    }
}