백준 9613번 GCD합 java

문제

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

입력

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

출력

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

 

 

각 쌍마다 최대공약수를 구해서 합을 구하는 단순한 문제

(브루트포스+GCD)

 

*답을 출력할 변수를 long형으로 선언해야함을 주의하자. (정답률 낮은 이유)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

9613번: GCD 합

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static int GCD(int n1, int n2) {
		if (n2 == 0) {
			return n1;
		} else {
			return GCD(n2, n1 % n2);
		}
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		ArrayList list = new ArrayList<>();

		int testCase = sc.nextInt();

		for (int i = 0; i < testCase; i++) {
			int n = sc.nextInt();

			list.clear();
			for (int j = 0; j < n; j++) {// 두번째 테스트케이스
				list.add(sc.nextInt()); // 숫자 넣어주기
			}
			long ans = 0;

			for (int x = 0; x < list.size() - 1; x++) {
				for (int c = x + 1; c < list.size(); c++) {
					ans += GCD(list.get(x), list.get(c));

				}
			}

			System.out.println(ans);
		}

	}

}