[SWEA] 3032 홍준이의 숫자 놀이 (Java)

1.  문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV-0U8FKZLQDFAXT&categoryId=AV-0U8FKZLQDFAXT&categoryType=CODE&problemTitle=3032&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

2.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    static final StringBuilder answer = new StringBuilder();
    static final Reader scanner = new Reader();

    static int a;
    static int b;

    static void input() {
        a = scanner.nextInt();
        b = scanner.nextInt();
    }

    static void solution() {
        int[] result = extendedEuclidean(a, b);
        if (result == null) {
            answer.append(-1).append('\n');
        } else {
            answer.append(result[0]).append(' ').append(result[1]).append('\n');
        }
    }

    static int[] extendedEuclidean(int a, int b) {
        int r0 = a, r1 = b;
        int s0 = 1, s1 = 0;
        int t0 = 0, t1 = 1;
        int temp = 0, q = 0;

        while (r1 > 0) {
            q = r0 / r1;
            temp = r0;
            r0 = r1;
            r1 = temp - r1 * q;
            temp = s0;
            s0 = s1;
            s1 = temp - s1 * q;
            temp = t0;
            t0 = t1;
            t1 = temp - t1 * q;
        }

        if (r0 != 1) {
            return null;
        } else {
            return new int[]{s0, t0};
        }
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();
        for (int testNum = 1; testNum <= T; testNum++) {
            answer.append('#').append(testNum).append(' ');
            input();
            solution();
        }

        System.out.print(answer);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

3.  접근

베주 항등식

정의

• GCD(a, b) = d라고 할 때,
  1. ax + by = d 를 만족하는 정수 x, y가 존재한다.
  2. d는 정수 x, y에 대하여 ax + by로 표현할 수 있는 가장 작은 정수이다.
  3. ax + by로 표현될 수 있는 모든 정수는 d의 배수이다.

확장 유클리드 호제법

• a, b의 최대 공약수와 ax + by = gcd(a, b)를 만족하는 x, y를 구하는 알고리즘

초기 조건

• $r_0 = a, r_1 = b$
• $s_0 = 1, s_1 = 0$
• $t_0 = 0, t_1 = 1$

동작

• $q_i = r_{i - 1} / r_i$
• $r_i = r_{i - 2} - r_{i - 1}q_i$
• $s_i = s_{i - 2} - s_{i - 1}q_i$
• $t_i = t_{i - 2} - t_{i - 1}q_i$