[ BOJ ][JAVA][2824] 최대공약수

https://www.acmicpc.net/problem/2824

2824번: 최대공약수

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	192 MB	6008	881	680	22.561%

문제

상근이는 학생들에게 두 양의 정수 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을 출력해야 한다)

예제 입력 1

3
2 3 5
2
4 5

예제 출력 1

10

예제 입력 2

4
6 2 3 4
1
1

예제 출력 2

1

예제 입력 3

3
358572 83391967 82
3
50229961 1091444 8863

예제 출력 3

000012028

접근

예제의 형태를 보고 바로 곱하면 안될 것이라는 것을 예상할 수 있었다.

arr1, arr2 의 각 수마다 각각 최대공약수를 구해주었고, 그렇게 구한 최대공약수는 해당 인덱스에 나눗셈을 해서 다음번에 또 수행되지 않도록 했다.

각 연산마다 구한 최대공약수를 곱하여 answer라는 변수에 담았고, 범위를 벗어날경우 모듈러 연산을 수행함과 동시에 boolean 변수로 9자리가 되어야 함을 판단해서 "0"을 맨 마지막에 붙여주었다.

코드

/**
 * BOJ 2824 최대공약수
 * 수학, 정수론, 구현
 */
import java.io.*;
import java.util.*;

public class p2824 {
    static final int MOD = 1000000000;
    static int n, m, a, b;
    static int[] arr1, arr2;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr1 = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr1[i] = Integer.parseInt(st.nextToken());
        }

        m = Integer.parseInt(br.readLine());
        arr2 = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            arr2[i] = Integer.parseInt(st.nextToken());
        }

        long answer = 1;
        boolean flag = false;
        // 1000 * 1000
        for (int i = 0; i < n; i++) {
            if (arr1[i] == 1) continue;
            for (int j = 0; j < m; j++) {
                if (arr2[j] == 1) continue;
                long gcd = gcd(arr1[i], arr2[j]);
                answer *= gcd;
                if (answer >= MOD) flag = true;
                answer %= MOD;
                // 예를들어 한번 2로 나누었으면 그 이후에는 2로 나누지 않고 중복을 제거하기 위해
                arr1[i] /= gcd;
                arr2[j] /= gcd;
            }
        }

        String str = String.valueOf(answer);
        StringBuilder sb = new StringBuilder();
        if (str.length() < 9 && flag == true) {
            while (sb.length() + str.length() < 9) {
                sb.append("0");
            }
        }
        sb.append(answer);
        System.out.println(sb.toString());
    }

    // 유클리드 호제법 : O(logN)
    static int gcd(int p, int q) {
        if (q == 0) return p;

        return gcd(q, p % q);
    }
}