9613. GCD 합 (자바, Java)

무식하게 브루트-포스로 이중for문 돌렸다.

재귀와 반복문 중에는, 반복문이 가능한 경우에는 반복문쪽으로 돌리고 있다. 똑같이 구현하면 재귀보단 반복문이 시간상 우위에 있다보니 습관을 들이는 중.

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
				
		for (int i=0; i<t; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int n = Integer.parseInt(st.nextToken());
			int[] k = new int[n]; // 각 값을 넣을 배열 생성
			long ans = 0; // 출력하게 될 각 줄의 정답값
			for (int j=0; j<n; j++) {
				k[j] = Integer.parseInt(st.nextToken());
			}
			for (int j=0; j<n-1; j++) {
				for (int l=j+1; l<n; l++) {
					ans+=gcd(k[j], k[l]);
				}
			}
			sb.append(ans + "\n");
		}
		System.out.println(sb);
	}
	
	public static int gcd (int minor, int major) {
		int a=minor;
		int b=major;
		while (b%a!=0) {
			int temp = a;
			a = b%a;
			b = temp;			
		}
		
		return a;
	}

}