백준 JAVA 9613 GCD 합

문제 링크: https://www.acmicpc.net/problem/9613

9613번: GCD 합

 

▶ 해설

---

n 개의 수가 주어집니다. 각각의 숫자마다의 GCD (최소 공약수)를 구한 후 더한 것을 출력합니다.

 

import java.math.BigInteger;
import java.util.*;
import java.io.*;
 
 
 
 
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 tc = 0; tc < t; tc++) {
            String [] str = br.readLine().split(" ");
            int n = Integer.parseInt(str[0]);
            int []arr = new int[n];
            for(int i=0;i<n;i++) {
                arr[i] = Integer.parseInt(str[i+1]);
            }
            long sum=0;
            for(int i=0;i<n;i++) {
                for(int j=i;j<n;j++) {
                    if(i!=j) {
                        sum+=gcd(arr[i],arr[j]);
                    }
                }
            }
            System.out.println(sum);
        }
    }
    public static int gcd(int a, int b) {
        if(b==0) return a;
        return gcd(b,a%b);
    }
}