챕터4-2. 수학 | 최대공약수, 최소공배수(GCD, LCM)

최대공약수(GCD, Greatest Common Divisor)

# 한줄요약
- 최대공약수를 구할 땐 유클리드 호제법을 이용하자.

 

# 개념

- 최대공약수는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.

- 최대공약수가 1인 두 수를 서로소(Coprime)라고 한다.
- 3개 이상의 수에 대한 최대공약수를 구해야 하는 경우 GCD(GCD(A,B), C) 이런 방식으로 2개씩 묶어서 계산하면 된다.

 

@ 최대공약수를 구하는 첫 번째 방법 => 시간복잡도 : O(N)
- a와 b를 2 ~ min(a,b) 까지의 모든 정수로 나누어 보는 것.
- 가장 쉬운 방법

int g = 1; // 모든 경우에 두 수는 공약수 1을 가지기 때문에 1로 초기화함

for(int i = 2; i <= min(a, b); i++)
{
    if (a % i == 0 && b % i == 0)
        g = i;
}

@ 최대공약수를 구하는 두 번째 방법 => 가장 효율적임
- 유클리드 호제법(Euclidean algorithm) 이용
- 이는 gcd(a, b) -> gcd(b, a%b) 이를 반복적으로 계속 진행하여, 오른쪽 인자의 값이 0일 때 왼쪽 인자를 반환하는데 
   이것이 최대공약수이다.
- a < b 인 경우 둘의 위치를 swap 시킨뒤 계산되도록 하는 코드들이 간혹 있는데, 이 과정은 필요가 없다.
   a < b 일 때 a%b = a가 되기 때문에 계산중 알아서 swap이 일어나기 때문이다.

// 재귀적인 방법
int gcd(int a, int b)
{
    if (b == 0)
        return a;            // b가 0이 되었을 때의 a가 최대공약수임
    else
        return gcd(b, a%b);
}

// 비재귀적인 방법
int gcd(int a, int b)
{
    while(b != 0)  
    {
        int r = a % b;
        a = b;
        b = r
    }
    return a;        // b가 0이 되었을 때의 a가 최대공약수임
}

최소공배수(LCM, Least Common Multiple)

# 한줄요약
- 최소공배수를 구할 땐 유클리드 호제법으로 최대공약수 G를 구하고, L x G = A x B 를 이용해 L을 구하자.

# 개념
- 최소공배수는 A와 B의 공통된 배수 중에서 가장 작은 정수이다.
- 최대공약수와 달리 최소공배수는 두 수 A, B보다 큰 수가 나올 수 있기 때문에 저장할 때 적절한 자료형을 선택해야한다.
   L = (A x B) / G 에 의해서 (A x B)의 값이 int형을 넘는지 안넘는지 체크해야함.

@ 최소공배수를 구하는 방법
- 최대공약수를 구하는 방법을 응용하면 쉽게 구할 수 있다. L x G = A x B 이므로 L = (A x B) / G 이다.
- G는 유클리드 호제법으로 구하여 사용하자.

위 개념을 적용한 문제풀이

# 최대공약수와 최소공배수를 구하는 문제
- https://www.acmicpc.net/problem/2609

- A, B는 1 ~ 10,000 이므로, 둘 다 최대로 10,000 일 때 A x B = 100,000,000 (1억) 이므로  
   int형의 저장범위를 벗어나지 않기 때문에 자료형은 크게 신경쓰지 않아도 된다.

 

# 최소공배수를 구하는 문제
- https://www.acmicpc.net/problem/1934
-  A, B는 1 ~ 45,000 이므로 둘 다 최대로 45,000 일 때 A x B = 2,025,000,000 (20억) 이므로
   int형의 저장범위를 벗어나지 않기 때문에 자료형은 크게 신경쓰지 않아도 된다.

# 최대공약수의 합 문제
- https://www.acmicpc.net/problem/9613

- N개의 수가 주어지면 2개씩 짝지어서 각각의 GCD를 구하여 모두 더하는 문제
- n이 1 ~ 100의 범위이고, n개의 수의 범위는 1 ~ 1,000,000인데,
   n개인 수들을 2개씩 짝지어 만드는 모든 경우의 수는 n(n-1) / 2 이다.
   그러면 이 짝에서 n(n-1) / 2개의 최대공약수들이 나오는데 그 수는 1 ~ 1,000,000의 범위를 가지므로
   총 합의 최대범위는 100*99 / 2 * 1,000,000 = 4,950,000,000(49억)이다.
   이는 int형의 표현범위 +-21억 을 넘고, unsigned int형의 표현범위 +42억을 넘어서는 값으로
   long long 형을 사용해야 한다.(long long 형의 저장범위는 +-900경)