9613.GCD합

문제

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

입력

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

출력

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	33868	13838	11355	41.641%

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

풀이

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  

public class GCD의합 {  
    public static void main(String[] args) throws IOException {  

        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));  

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

        for(int i=0; i<t; i++){  
            String[] arr = br.readLine().split(" ");  

            long answer = 0;  

            int n = Integer.parseInt(arr[0]);  

            int[] intArr = new int[n];  

            for(int j=0; j<intArr.length; j++){  
                intArr[j] = Integer.parseInt(arr[j+1]);  
            }  

            for(int j=0; j<intArr.length-1; j++){  
                for(int k= j+1; k<intArr.length; k++){  
                    answer += gcd(intArr[j], intArr[k]); //모든케이스를 전부 확인한다.  
                }  
            }  

            System.out.println(answer);  
        }  

        br.close();  

    }  

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