[BaekJoon-9613] GCD 합

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

예제 입력 1

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

예제 출력 1

70
3
35

해결

가능한 모든 두 수의 쌍에 유클리드 호제법을 적용한다. 바깥 반복은 첫 수의 인덱스 i, 안쪽 반복은 그보다 큰 j를 선택한다. 마지막 원소는 뒤에 짝이 없으므로 바깥 반복의 마지막 시작점이 되지 않는다.

한 쌍을 정확히 한 번 세기

n개 수에서 서로 다른 두 인덱스를 고르는 쌍은 n(n−1)/2개다. 바깥 인덱스 i 다음의 j>i만 방문하면 (a,b)와 (b,a)를 중복 계산하지 않는다. 10, 20, 30, 40의 여섯 쌍의 GCD는 순서대로 10, 10, 10, 10, 20, 10이므로 합은 70이다. 기존 설명의 “20,30,40의 최대공약수”처럼 여러 수를 한꺼번에 묶는 문제가 아니다.

각 쌍의 최대공약수는 유클리드 알고리즘으로 구한다. 예를 들어 gcd(30,40)는 gcd(40,30)→gcd(30,10)→gcd(10,0)=10이다. 인덱스 i와 j가 가리키는 두 값을 그때 읽어 더하며, 원본 수를 정렬할 필요는 없다.

한 쌍의 GCD는 최대 1,000,000이다. 쌍이 최대 4,950개라 합은 49억 5천만까지 가능해 32비트 int를 넘는다. 코드가 누적합을 long으로 두는 이유다. 시간은 O(n² log V), V는 값의 최댓값이고 입력 한 줄을 보관하는 공간은 O(n)이다. 두 수만 주어져도 한 쌍을 계산하고, 서로 같은 값 두 개도 인덱스가 다르면 유효한 쌍이다.

첫 수	뒤에 오는 짝	GCD의 합
10	20, 30, 40	10+10+10=30
20	30, 40	10+20=30
30	40	10
합계	여섯 쌍	70

표의 행마다 첫 수를 고정하면 코드의 이중 반복이 보인다. 이 방법은 값이 같은 두 원소도 서로 다른 입력 위치라면 한 쌍으로 센다. 합계는 처음부터 long sum에 누적한다. 중간 합이 int에서 넘친 뒤에는 출력할 때 long으로 바꿔도 원래 값을 복구할 수 없다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        sumOfGCD();
    }

    public static void sumOfGCD() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());

        while (t-- != 0) {
            String s = in.readLine();
            String[] split = s.split(" ");
            int n = Integer.parseInt(split[0]);
            long sum = 0;
            for (int i = 1; i <= n - 1; i++) {
                for (int j = i + 1; j <= n; j++) {
                    sum += gcd(Integer.parseInt(split[i]), Integer.parseInt(split[j]));
                }
            }
            out.write(sum + "\n");
            out.flush();
        }
        out.close();
        in.close();
    }

    public static long gcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}