SWEA 3032 홍준이의 숫자 놀이

1 개요

SWEA 3032 홍준이의 숫자 놀이

SW Expert 아카데미

#	문제	풀이

3 Java

import java.util.*;
public class Solution {
	public static int[] xgcd(int a, int b){
		int[] result = {0,0,0};
		int[] aa = {1,0}; 
		int[] bb = {0,1};
		int q = 0;
		while(true) {
			q = a / b;
			a = a % b;
			aa[0] = aa[0] - q*aa[1];
			bb[0] = bb[0] - q*bb[1];
			if (a == 0) {
				result[0] = b;
				result[1] = aa[1];
				result[2] = bb[1];
				return result;
			}
			q = b / a;
			b = b % a;
			aa[1] = aa[1] - q*aa[0];
			bb[1] = bb[1] - q*bb[0];
			if (b == 0) {
				result[0] = a;
				result[1] = aa[0];
				result[2] = bb[0];
				return result;
			}
		}
	}
	public static void main(String[] args) {
		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 = xgcd(A, B);
			if( result[0] != 1 ) System.out.format("#%d %d\n", tc, -1);
			else System.out.format("#%d %d %d\n", tc, result[1], result[2]);
		}
		sc.close();
	}
}

import java.util.*;
public class Solution {
	static int x1, y1, x2, y2;
	static int solve(int a, int b) {
		x1 = 1; y1 = 0;
		x2 = 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;
		}
	}
	public static void main(String[] args) {
		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);
		}
		sc.close();
	}
}

4 같이 보기

• 함수 xgcd()