백준 2824 최대공약수 (Java)

1. 문제

상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.

상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.

이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다.

셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, M개의 수를 곱하면 B가 된다.

출력

두 수의 최대공약수를 출력한다. 만약, 9자리보다 길다면, 마지막 9자리만 출력한다. (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)

 

2. 풀이

10억짜리 숫자가 천 개 있다면 이는 long 형을 벗어난다. 자바에는 BigInteger라는 라이브러리가 존재한다.

        for (int i = 0; i < n; i++) {
            a = a.multiply(new BigInteger(split[i]));
        }

두 수는 다음과 같이 곱할 수 있다.

 

        String ans = a.gcd(b).toString();

두 수의 최대공약수는 이와 같이 구할 수 있다. 이를 끝에서부터 9자리를 출력하면 정답을 구할 수 있다.

3. 코드 전문

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

public class Main {

    static int n;
    static int m;

    static BigInteger a = BigInteger.ONE;
    static BigInteger b = BigInteger.ONE;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(reader.readLine());

        String temp = reader.readLine();
        String[] split = temp.split(" ");
        for (int i = 0; i < n; i++) {
            a = a.multiply(new BigInteger(split[i]));
        }

        m = Integer.parseInt(reader.readLine());

        temp = reader.readLine();
        split = temp.split(" ");
        for (int i = 0; i < m; i++) {
            b = b.multiply(new BigInteger(split[i]));
        }

        String ans = a.gcd(b).toString();

        System.out.println(ans.length() > 9 ? ans.substring(ans.length() - 9) : ans);


    }

}