標準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