[SWEA] - 3032. 홍준이의 숫자 놀이 (D3)

[문제]

숫자를 좋아하는 홍준이는 다음과 같은 놀이를 하고 있다.
서로소인 두 자연수 A와 B를 정한 후, Ax + By = 1이 되는 x와 y를 계산하는 것이다.
홍준이는 A와 B가 작을 때에는 암산으로 쉽게 계산할 수 있었는데, 두 수가 클 때의 계산에는 어려움을 느끼고 있다.
여러분은 홍준이를 도와, 두 자연수 A와 B가 주어졌을 때에 Ax + By = 1이 되는 x와 y를 계산하는 프로그램을 작성하시오.

[입력]
첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10,000)
각 테스트케이스의 첫째 줄에 두 자연수 A와 B가 주어진다. (1 ≤ A, B ≤ 109)

[출력]
각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(테스트케이스 번호) “를 출력하고, Ax + By = 1이 되는 x와 y를 출력한다.
가능한 x와 y 쌍이 유일하지 않다면, 아무것이나 출력해도 된다.
가능한 해가 없는 경우에는 -1을 출력한다.

문제 풀기

3032. 홍준이의 숫자 놀이

 

---

[풀이]

• 확장 유클리드 호제법을 통해 풀이
  👉 ax+by=c이 주어질 때 이 방정식을 만족하는 (x, y)값을 구할 수 있다.

확장 유클리드 알고리즘

import java.util.Scanner;

class Solution {	
	public static int x1, x2, y1, y2;
	
	public static void main(String[] args) throws Exception {		
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			int result = solve(a, b);
			
			if(result == 1) System.out.format("#%d %d %d\n", tc, x1, y1);
			else if(result == 2) System.out.format("#%d %d %d\n", tc, x2, y2);
			else System.out.format("#%d %d\n", tc, -1);
		}
	}
	
	public static int solve(int a, int b) {
		x1 = 1; x2 = 0;
		y1 = 0; y2 = 1;
		
		while(true) {
			if(a==1) return 1;
			if(b==1) return 2;
			if(a==0 || b == 0) return 0;
			
			x1 -= a / b * x2;
			y1 -= a / b * y2;
			
			a %= b;
			
			x2 -= b / a * x1;
			y2 -= b / a * y1;
			
			b %= a;
		}
	}
}