[알고리즘] 유클리드 호제법

유클리드 호제법?

 

 두 양의 정수, 혹은 두 다항식의 최대공약수(gcd)를 구하는 방법을 말한다. gcd, lcm관련 문제를 풀 때 거의 필수적으로 사용된다고 느껴질 정도로 많이 사용되는 것 같다.

 

 

두 양의 정수 a,b(a>b)에 대하여 a = bq+r (0<=r<b)라고 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다.
즉, gcd(a,b) = gcd(b,r) (r=a%b)
r=0이라면, a,b의 최대공약수는 b가 된다.

예시)
1071과 1029의 최대공약수를 구하면,
1. 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지 42를 구한다.
2. 1029는 42로 나누어떨어지지 않기 때문에 1029를 42로 나눈 나머지 21을 구한다.
3. 42는 21로 나누어떨어지므로, 1071과 1029의 최대공약수는 21이다.

 

 

M으로 모든 숫자들을 나누었을 때, 나머지가 같다면 M은 임의의 두 수의 차이의 약수가 된다. 즉, M은 두 숫자의 차이 값들의 공약수가 된다.

1<=K<=100인 k개의 자연수가 있다고 하자. 이때, M으로 나눈 나머지가 t로 모두 같다고 하면 다음과 같은 식이 성립한다.

이 식을 이용하여 임의의 i,j에 대해서 Ni-Nj = 0(mod M) 이고, 두 개의 숫자의 차이는 M으로 나누어짐을 알 수 있다.

 

 

따라서 최대공약수는 다음과 같이 구할 수 있다.

int gcd(int a, int b) {
    if(a%b ==0) {
        return b;
    }
    return gcd(b, a%b);
}

또한 최소공배수의 경우 두 수의 곱을 최대공약수로 나눈 것과 같다.

int lcm(int a, int b) {
    return a*b/gcd(a,b);
}