[백준] 300 - 수학 1 : GCD 합 (9613번 JAVA)

[백준] 300 - 수학 1 : GCD 합 (9613번 JAVA)

---

[주의점]

각 케이스별 gcd의 최대값은 1,000,000 * 1,000,000 이다. => int로 담을 수 없다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        long sum = 0;

        for(int k=0; k<t; k++){

            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int[] arr = new int[n];

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

            sum = 0;

            for(int i=0; i<n-1; i++){
                for(int j=i+1; j<n; j++){
                    sum += gcd(arr[i], arr[j]);
                }
            }

            bw.write(sum + "\n");
        }


        bw.flush();
        bw.close();
    }

    // Greatest Common Divisor (최대 공약수)
    public static int gcd(int a, int b){
        while(b != 0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}