[백준] 9613. GCD 합 (Java)

 

🔒 문제

9613번: GCD 합

 

🔑 알고리즘

유클리드 호제법

 

 

💡  풀이

문제에서 주어진대로 각 쌍마다 최대공약수를 계산해 더한다.

최대공약수를 구하는데 유클리드 호제법을 이용한다.

 

* n이 100이고 모든 값이 1,000,000 이라면 sum의 값은

100C2 * 1,000,000 = 4,950 * 1,000,000 = 4,950,000,000 로 int 범위를 초과하므로 long 자료형을 사용한다.

 

✏️ 코드

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

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 t = 0; t < T; t++) {
			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());

			long sum = 0;
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					sum += arr[i] > arr[j] ? gcd(arr[i], arr[j]) : gcd(arr[j], arr[i]);
				}
			}
			System.out.println(sum);
		}
	}

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