[14565] 역원(Inverse) 구하기 (JAVA)

# 문제 설명

집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다.

정수 N, A가 주어졌을 때 Zn에서의 A의 덧셈역과 곱셈역을 구하시오.

단, 곱셈역을 구할 수 없으면 -1을 출력한다.

---

입력

첫 번째 줄에 N(2 ≤ N ≤ 1012)과 A(1 ≤ A < N)이 주어진다.

---

출력

첫 번째 줄에 A의 N에 대한 덧셈역과 곱셈역을 한 줄에 공백으로 구분하여 출력한다.

 

# 정답 코드

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());
        StringBuilder sb = new StringBuilder();

        long N = Long.parseLong(st.nextToken());
        long A = Long.parseLong(st.nextToken());

        //덧셈역
        long B = N - A;
        sb.append(B + " ");

        //곱셈역 (a*c와 n은 서로소)
        if (GCD(A, N) != 1) {
            sb.append("-1");
        }
        else {
            long[] result = Execute(A, N);

            while (result[0] < 0) {
                result[0] += N;
            }

            sb.append(result[0]);
        }

        System.out.print(sb);
    }

    //ax + by = c
    public static long[] Execute(long a, long b) {
        long[] xy = new long[2];

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

        long q = a / b;
        long[] prev = Execute(b, a % b);
        xy[0] = prev[1]; //x = y'
        xy[1] = prev[0] - prev[1] * q; //y = x' - y' * q

        return xy;
    }

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

        while (true) {
            result = big % small;

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

            big = small;
            small = result;
        }
    }
}

 

덧셈역은 N - A로 구한다.

곱셈역은 확장 유클리드 호제법을 이용하여 구한다.

확장 유클리드 호제법을 이용하여 구한 몫 중 x의 값이 곱셈역이 된다.