[알고리즘] 최대 공약수 구하기 - 유클리드 호제법

참고: [최대공약수 쉽게 구하는 법] - 유클리드 호제법

 

최대 공약수를 구하는 방법은 여러 가지가 있다.

1. 보통 방법 (연제법) - 동시에 나눌 수 있는 수로 계속 나누는 방법
2. 소인수분해 - 소수의 곱으로 표현하는 것
3. 유클리드 호제법\

 

유클리드 호제법

두 수 A, B 가 있을 때 A, B의 최대 공약수 G에 대하여 다음이 성립한다. (a, b는 서로소)

A = G*a

B = G*b

따라서 다음도 성립한다.

A - B = Ga - Gb = G * (a -b)

두 수의 차 A-B는 최대공약수 G의 배수이다.

이를 통해 A-B의 약수 중 A와 B를 나누어 떨어지게 하는 수 중 가장 큰 수를 구하면 된다.

 

더 나아가 B와 A-B의 최대 공약수를 구하는 식으로 계속 반복해 적용할 수 있다.

119 - 91 = 28
91 - 28 - 28 - 28 = 7 (큰 수 119는 버리고 91에서 28을 3번 뺄 수 있다. 나머지는 7 이다.)
18 - 7 -7 -7-7 = 0 (큰 수 91은 버리고 28에서 7을 4번 뺄 수 있다. 나머지는 0이다.

결론적으로 차가 0 일 때 빼는 수가 바로 최대 공약수이다.

 

연습 문제 - BOJ 9613 GCD의 합

1.  가능한 조합 구하기
2. 최대 공약수 구하기
3. 결과에 합하기

조합을 구하기 위해 Combination 함수를 작성했고, 조합을 구한 후 findGDC로 최대 공약수를 구했다.

findGDC에서 유클리드 호제법을 사용해서 b - a를 수행하기 때문에 배열(arr)을 입력받은 후 정렬해 줬다.  

 

솔루션

 

import java.io.*;
import java.util.*;

/*
가능한 모든 쌍의 최대공약수의 합
1. 조합 구하기
2. 최대 공약수 구하기 -> 더하기
- 유클리드 호제법 b - a 사용
*/
public class Main {
    static int t;
    static int[] arr;
    static boolean[] visited;
    static int[] output;
    static long result; // 총 합이 int 범위를 벗어난다. 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        t = Integer.parseInt(br.readLine());
        
        for (int i=0; i < t; i++) {
            arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            Arrays.sort(arr, 1, arr[0]+1); // 1 ~ n 요소 정렬
            
            output = new int[2];
            visited = new boolean[arr[0]+1];
            result = 0L; // GCD 총합
            
            combination(0, 1);
            System.out.println(result);
        } 
    }
    
    public static void combination(int depth, int s) {
        if (depth == 2) {
            result += (long) findGCD(output[0], output[1]);
            return;
        }
        
        for (int i=s; i <= arr[0]; i++) {
            if (visited[i]) continue;
            
            visited[i] = true;
            output[depth] = arr[i];
            combination(depth + 1, i);
            visited[i] = false;
        }
    }
    
    // 항상 a < b
    public static int findGCD(int a, int b) {
        while (a > 0 && b > 0) {
            if (b % a == 0) return a;
            if (b - a > 0) {
                int tmp = a;

                a = b % a;
                b = tmp;
            } 
        }
        
        return 1;
    }
}