[백준] 9613 : GCD 합 JAVA 풀이

 

자료형을 주의해야 하는 것만 빼면 간단한 문제였다.

만약 한 테스트케이스가 100개의 수로 이루어져 있으면 그 순서쌍의 개수만 해도 아주 커진다.

그렇기 때문에 그 모든 순서쌍의 합인 sum의 자료형은 long으로 선언하는 것이 바람직하다.

 

 

1. 테스트케이스의 개수 T를 입력받는다.

2. T개의 테스트케이스를 한 줄씩 입력받는다.

3. 테스트케이스의 내용 중 첫 번째 값인 n이 한 테스트케이스를 구성하는 숫자의 개수다.

4. n개의 수를 입력받아 ArrayList에 저장한다.

5. gcd를 구하는 메서드를 작성한다.

5. 이중 반복문으로 모든 순서쌍을 gcd 메서드에 인사로 넘겨주고, gcd의 합을 구한다.

6. 각 테스트케이스의 gcd 합을 출력한다.

 

 

 

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));
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0;i<T;i++) {
			long sum = 0;
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			ArrayList<Integer> list = new ArrayList<>();
			
			for(int j=0;j<n;j++) {
				
				list.add(Integer.parseInt(st.nextToken()));
			}
			
			for(int k=0;k<n-1;k++) {
				for(int l=k+1;l<n;l++) {
					sum += gcd(list.get(k),list.get(l));
				}
			}
			System.out.println(sum);
			
		}
	}
	static int gcd(int a, int b) {
		while(b!=0) {
			int r = a%b;
			
			a = b;
			b = r;
		}
		return a;
	}

}