[JAVA] 백준 9613번- GCD 합

https://www.acmicpc.net/problem/9613

9613번: GCD 합

 

 

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

public class Main{

    public static int gcd(int a, int b){
        if(b==0) return a;
        else return gcd(b, a%b);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());

        ArrayList<Integer> list = new ArrayList<>();

        StringTokenizer st;
        while(t-->0){
            long sum = 0;
            list.clear();
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            for(int i=0; i<n; i++){
                list.add(Integer.parseInt(st.nextToken()));
            }
            for(int i=0; i<list.size(); i++){
                for(int j=i+1; j<list.size(); j++){
                    sum += gcd(list.get(i), list.get(j));
                }
            }
            sb.append(sum).append("\n");
        }
        System.out.println(sb);
    }
}

 

여기서 GCD란 최대공약수를 말한다.

유클리드 호제법을 이용하면 최대공약수를 쉽게 찾을 수 있다.

a와 b의 최대공약수를 구하고자 할 때, a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다. 이에 따라 b를 r로 나눈 나머지 r0를 구하고, 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

입력받은 수들을 리스트에 넣고, 브루트포스로 모든 원소들의 쌍을 탐색하여 최대공약수의 합을 구한다. 

 

이 때 주의할 점은 입력으로 주어지는 수의 범위가 1,000,000까지 이므로 입력 값들의 합인 답을 long형으로 해줘야 한다.