[백준 - JAVA] GCD 합

9613번: GCD 합 (acmicpc.net)

9613번: GCD 합

http://boj.kr/68677a80d1384df2a08a6a8b4e4f41b3

공유 소스 보기

import java.util.Scanner;

class Main{
    
    public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int testCaseCount = sc.nextInt(),
			inputCount, x, y, tmp;
        
		long result;
        
		int[] intArr;
		
		for(int i = 0; i < testCaseCount; i++) {
			
			inputCount = sc.nextInt();
			result = 0;
			
			intArr = new int[inputCount];
			
			for(int j = 0; j < intArr.length; j++) {
				
				intArr[j] = sc.nextInt();
				
			}
			
			for(int j = 0; j < intArr.length; j++) {
				
				
				for(int k = j + 1; k < intArr.length; k++) {
					
					x = intArr[j];
					y = intArr[k];
					
					while(true){
						
						tmp = y;
						y = x % y;
						x = tmp;
						if(y == 0) break;
						
					}
					
					result += tmp;
					
				}
				
			}
			
			System.out.println(result);
			
		}
		
	}
    
}

 

유클리드 호제법 이용해서 풀어주면 된다.