[JAVA] 백준 (실버4) 9613번 GCD 합

링크

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

---

문제 설명

(정답률 41.607%)
양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

---

입력 예제

3
4 10 20 30 40
3 7 5 12
3 125 15 25

---

출력 예제

70
3
35

---

정답 코드

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;

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(st.nextToken());
            int[] arr = new int[n];
            long answer = 0;

            for (int j = 0; j < n; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }

            for (int j = 0; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    answer += GCD(arr[j], arr[k]);
                }
            }

            System.out.println(answer);
        }

    }

    static long GCD(int a, int b) {
        if (b == 0) return a;
        return GCD(b, a % b);
    }
}

---

정리

문제 자체는 간단하다.
하지만 정답률이 낮은 이유는 정답의 타입 때문이다.
주어진 N이 범위는 100까지지만 입력으로 들어온 수의 최대값은 100만이다.
N이 100이고 모든 수가 100만일 때 $100C2 * 1,000,000 = 49.5$억이므로 int의 범위를 초과한다.
int의 표현 범위는 -2,147,483,648 ~ 2,147,483,647이다.
그래서 정답은 long형으로 선언하여야 한다.