[Java] 백준 21568 Ax+By=C - 확장 유클리드 호제법

백준 21568 Ax+By=C
문제
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.StringTokenizer;
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		long gcd = gcd(a, b);
		if(c%gcd != 0) {
			System.out.println(-1);
		} else {
			int mok = (int) (c / gcd);
			long[] ret = Excute(a, b);
			System.out.println(ret[0] * mok + " " + ret[1] * mok);
		}
	}
	private static long[] Excute(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 = Excute(b, a % b);
		ret[0] = v[1];
		ret[1] = v[0] - v[1] * q;
		return ret;
	}
	private static long gcd(long a, long b) {
		while(b != 0) {
			long temp = a % b;
			a = b;
			b = temp;
		}
		return Math.abs(a);
	}
}

예제

1 2 3

 

3 4 5

 

6 8 3

결과

백준 21568 Ax+By=C

 

21568번: Ax+By=C