유클리드 호제법 ( 최대공약수 구하기 )

Table of Contents

개요

유클리드 호제법

시간복잡도

최대공약수에 대해 알아둬야 할 것

문제

1. 개요

 두 수 n, m 의 최대공약수를 구할 때, 유클리드 호제법을 이용하면 시간복잡도 O(log(n+m))만에 구할 수 있습니다.

2. 유클리드 호제법

 gcd(n,m) = gcd(n-m,m), 그리고 더 나아가 gcd(n,m) = gcd(n%m,m) 임을 이용해 최대공약수를 빠르게 찾는 방법입니다. (n,m 은 자연수) (편의상 n, m 의 최대공약수 = gcd(n,m) 으로 표현하겠습니다.)

n,m 은 자연수이고 n%m!=0 일 때, gcd(n,m) = gcd(n%m,m)이다.

증명

g = gcd(n,m), k = gcd(n%m,m), x =  n을 m으로 나누었을 때 몫이라고 하겠습니다. (n = x*m + n%m 이 성립합니다.)

1) g는 k의 배수이다.

m은 k의 배수입니다. ( k = gcd(n%m,m)이기 때문입니다. )

n 은 k의 배수입니다. (n = x*m + n%m = x*k의 배수 + k의 배수 = k의 배수)

그러므로 g는 k의 배수가 됩니다.

2) k는 g의 배수이다.

m은 g의 배수입니다. ( g = gcd(n,m)이기 때문입니다. )

n%m 또한 g의 배수입니다. (n%m = n - x*m= g의 배수 - x*g의 배수 = g의 배수)

그러므로 k는 g의 배수가 됩니다.

1) 과 2) 를 종합하면 k=g.

 gcd(n,m)을 gcd(n%m,m)으로 바꾸는 과정을 한 쪽이 0이 될 때 까지 진행하면 다음과 같이 구현할 수 있습니다.

// code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
 
using namespace::std;
 
int get_gcd(int v1,int v2){
    if(v1>v2) swap(v1,v2);
    if(v1==0) return v2;
    return get_gcd(v2%v1,v1);
}

3. 시간복잡도

 일반성을 잃지 않고, n >= m 이라고 가정하겠습니다. ( n = max(n,m) )

 이 때, m >= n%m 임은 나머지 연산의 특성을 고려하면 자명합니다.

 그러므로 아래와 같이 get_gcd가 호출됩니다.

 get_gcd(n,m) -> get_gcd(n%m, m) -> get_gcd(m%(n%m), n%m)

 이 때, get_gcd(m%(n%m), n%m) 가 호출될 때까지 상수 번의 연산이 필요했음은 자명합니다. ............ 1

 m%(n%m), n%m 중 최댓값은 n%m 입니다. ................. 2

 n>=m 일 경우, n > 2*(n%m) 이 성립합니다. ....................3

n>=m 이므로

n = x*m + n%m ( x = 자연수) 꼴로 n을 나타낼 수 있습니다.

n > 2*(n%m)

<-> x*m + n%m > 2*(n%m)

<-> x*m > n%m

x*m >= m > n%m 이 성립하므로 x*m > n%m이 성립합니다.

따라서 n > 2*(n%m) 이 성립합니다.

1, 2를 종합하면 상수 번의 연산으로 두 수 중 최댓값이 n에서 n%m 으로 바뀌었고, 이는 3에 의해 최댓값이 절반 이하가 되었음을 의미합니다. 이를 통해 위 소스의 시간복잡도는 O( log ( max(n,m) ) ) 임을 증명할 수 있습니다. 상수 번의 연산으로 최대값이 절반 이하가 되었기 때문이지요. 또한 이를 간단한 표기로 바꾸면 O( log(n+m) ) 이 됩니다.

4. 최대공약수에 대해 알아둬야 할 것

(1) LCM (a, b) = a * b / gcd (a, b) 이다. (* LCM (a, b) = a와 b의 최소공배수)

(2) gcd (a, gcd (b, c)) = gcd(gcd(a, b), c) 가 성립한다.

이 특징으로 인해 '구간에 있는 모든 수들의 gcd' 가 필요할 때, Segment tree 나 Sparse table 을 활용해 볼 수 있습니다.

5. 문제

(0) [BOJ 2609] 최대공약수와 최소공배수

(1) [BOJ 1188] 음식 평론가

※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.

※ 문의 : rikang93@gmail.com