[백준] 2824번 - 최대공약수 (Gold 5)

문제 링크

백준 2824번 - 최대공약수 (Gold 5)

문제 설명

N개의 수의 곱인 A와 M개의 수의 곱인 B의 최대공약수를 구하시오.
주어지는 N + M개의 수는 모두 1,000,000,000보다 작은 양의 정수이며, $1\leq N, M\leq 1000$이다.
최대공약수가 매우 커질 수 있으므로, 최대공약수가 10자리 이상이면 마지막 9자리만 출력하시오.

정답 코드 및 설명

각 수를 모두 소인수분해하고 지수들끼리 합해주면 A와 B를 소인수분해한 것이 된다.
두 수가 소인수분해가 되어있다면, 최대공약수는 각 소인수들의 지수 중 작은 것만 택하여 곱하면 된다.
예를 들어, $A = 2^{3} \times 3^{2}, B = 2^{2} \times 3^{3}$이면 $gcd(A, B) = 2^{2} \times 3^{2}$이다.
아래 코드에서는 소인수와 지수를 Map의 형태로 저장하였다.

출력에 주의해야하는데, 단순히 1,000,000,000으로 나눈 나머지를 빈 자리를 0으로 채워서 출력하면 안된다.
최대공약수가 10인 경우 000000010이 아닌 10이 출력되어야하기 때문이다.
이를 해결하기 위해 최대공약수가 1,000,000,000 이상인지 아닌지를 소인수들을 곱하는 과정에서 체크해야 하는데, 이 부분이 코드의 gcdIsBig에 해당한다.

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

public class BOJ2824 {
    final int MAX = 1_000_000_000;
    int[] a, b;
    boolean gcdIsBig = false;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(br.readLine());
        b = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            b[i] = Integer.parseInt(st.nextToken());
    }

    HashMap<Integer, Integer> factorization(int[] a) {
        HashMap<Integer, Integer> factors = new HashMap<>();
        for (int n : a) {
            factors = factorization(n, factors);
        }
        return factors;
    }

    HashMap<Integer, Integer> factorization(int n, HashMap<Integer, Integer> factors) {
        if (n == 1) return factors;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                factors.put(i, factors.getOrDefault(i, 0) + 1);
                return factorization(n / i, factors);
            }
        }
        factors.put(n, factors.getOrDefault(n, 0) + 1);
        return factors;
    }

    long pow(int prime, int order) {
        long pow = 1;
        while (order-- > 0) {
            pow *= prime;
            if (pow >= MAX) gcdIsBig = true;
            pow %= MAX;
        }
        return pow;
    }

    long gcd(HashMap<Integer, Integer> factorsA, HashMap<Integer, Integer> factorsB) {
        long gcd = 1;
        for (Integer primeA : factorsA.keySet()) {
            int orderA = factorsA.get(primeA);
            int orderB = factorsB.getOrDefault(primeA, 0);
            gcd *= pow(primeA, Math.min(orderA, orderB));
            if (gcd >= MAX) gcdIsBig = true;
            gcd %= MAX;
        }
        return gcd;
    }

    void solution() throws IOException {
        input();
        HashMap<Integer, Integer> factorsA = factorization(a);
        HashMap<Integer, Integer> factorsB = factorization(b);
        long gcd = gcd(factorsA, factorsB);
        if (gcdIsBig) System.out.printf("%09d", gcd);
        else System.out.println(gcd);
    }

    public static void main(String[] args) throws IOException {
        new BOJ2824().solution();
    }
}