BOJ) GCD 합 (9613 번)

GCD 합

9613번: GCD 합

GCD는 최대 공약수를 의미한다.

유클리드 호제법을 이용해서 쉽게 공약수를 구할 수 있다.

 

유클리드 호제법

위키에 따르면, 호제법이란 말은 두 수가 서로 상대 수를 나누어 원하는 수를 얻는 알고리즘 이라고 한다.

A와 B 라는 수가 있으면, A를 B로 나눈 나머지 A%B를 r이라고 한다. (단, A>B)

이 때, A와 B의 최대 공약수는 B와 r의 최대 공약수와 같다는 이론이다.

이 성질에 따라서, B를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나누는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수(분모)가 A와 B의 최대 공약수가 된다.

 

1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42

• 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21

• 42는 21로 나누어떨어진다.

따라서, 최대공약수는 21이다.

 

 

간단하게 코드로 구현하면 아래와 같다.

public static int gcd(int p, int q)
 {
	if (q == 0) return p;
	return gcd(q, p%q);
 }

 

코드

 

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

public class SumGCD_9613 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        final String NEW_LINE = "\n";

        while(t-- >0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int[] numArr = initNumArray(n, st);
            sb.append(solution(n, numArr)).append(NEW_LINE);
        }
        br.close();
        System.out.println(sb.toString());
    }

    private static int[] initNumArray(int n, StringTokenizer st) {
        int[] numArr = new int[n];
        for(int i=0; i<n; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }
        return numArr;
    }

    private static long solution(int n, int[] numArr) {
        long answer =0;
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                answer += gcd(numArr[i], numArr[j]);
            }
        }
        return answer;
    }

    private static int gcd(int left, int right) {
        while(right !=0) {
            int target = left;
            left = right;
            right = target % right;
        }
        return left;
    }
}