[21568] Ax+By=C (JAVA)

# 문제 설명

A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자.

• x, y는 정수
• 1,000,000,000 ≤ x, y ≤ 1,000,000,000

---

입력

첫째 줄에 정수 A, B, C가 주어진다.

---

출력

Ax+By=C를 만족하는 x, y를 공백으로 구분해 출력한다. 문제의 조건을 만족하는 (x, y)가 존재하지 않는 경우에는 -1을 출력한다.

 

# 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        //Ax + By = C
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        //C는 A,B의 최소 공배수의 배수여야 함
        int gcd = GCD(A, B);
        if (C % gcd != 0) {
            System.out.print("-1");
        }
        else {
            int mok = C / gcd;
            int[] result = Excute(A, B);
            System.out.print(result[0] * mok + " " + result[1] * mok);
        }
    }

    public static int[] Excute(int a, int b) {
        int[] xy = new int[2];

        if (b == 0) {
            xy[0] = 1; //x' = 1
            xy[1] = 0; //y' = 0
            return xy;
        }

        int q = a / b; //현재 보고 있는 몫
        int[] prev = Excute(b, a % b); //x', y'
        xy[0] = prev[1]; //x = y'
        xy[1] = prev[0] - prev[1] * q; //y = x' - y' * q

        return xy;
    }

    public static int GCD(int a, int b) {
        int big = Math.max(a, b);
        int small = Math.min(a, b);
        int result = 0;

        while (true) {
            result = big % small;

            if (result == 0) {
                return small;
            }

            big = small;
            small = result;
        }
    }
}

 

확장 유클리드 호제법을 이용하는 문제이다.

Ax + By = C에서 C는 A, B의 최대 공약수의 배수이다.

 

gcd에 GCD 함수를 사용하여 A와 B의 최대 공약수를 구해 저장한다.

C가 gcd의 배수가 아니면 -1을 출력하고 종료한다.

C가 gcd의 배수가 맞으면 x, y 값을 구한다.

 

C를 gcd로 나눈 몫을 mok에 저장한다.

Excute 함수를 사용하여 x, y를 구한다.

 

xy 배열에 x와 y를 저장한다.

만약 b가 0이면, 처음 시작하는 단계로 이전 x와 이전 y가 없으므로 x를 1, y를 0으로 지정한다.

q에는 현재 x를 y로 나눈 몫을 저장한다.

이전 x, 이전 y를 저장하는 prev 배열에 Execute 함수를 사용하여 구한다.

x = y', y = x' - y' * q 식으로 계산하여 x, y를 구해 리턴한다.

 

구한 x와 y에 구해뒀던 mok을 곱하여 출력한다.