백준 9613 / GCD합

문제

풀이

설명

t개의 케이스 각각의 n개 수들을 입력하고 입력한 수들의 GCD 합을 구한다.
이 문제는 유클리드 호재법을 이용해서 풀 수 있는 문제이다.

코드

import java.util.*;

public class Num9613 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		for (int k = 0; k < t; k++) {
			int n = sc.nextInt();
			int[] inputs = new int[n];
			
			for(int i = 0; i <n; i++) {
				inputs[i] = sc.nextInt();
			}
			
			long sum = 0;
			for (int i = 0; i < n-1; i++) {
				for (int j = i+1; j<n; j++) {
					sum += gcd(inputs[i], inputs[j]);
				}
				System.out.println(sum);
			}
		}
	}

	private static long gcd(int a, int b) {
		if(b==0) {
			return a;
		}
		return gcd(b,a%b);
	}
}

참고 :
출처 : https://www.acmicpc.net/problem/9613