유클리드 알고리즘은 두 정수의 최대 공약수를 구하는 효율적인 방법입니다. 이는 일반적으로 '나머지 연산을 이용한 재귀적 접근'으로 설명됩니다. 이를 수학적으로 표현하면 다음과 같습니다:
[hcf(u, v) = \begin{cases} u, & v = 0 \ hcf(v, u \bmod v), & v \neq 0 \end{cases}]
여기서 (u)와 (v)는 두 정수입니다. 이제 이를 증명해봅시다.
-
(u < v)인 경우: (u \bmod v = u)이므로 (hcf(v, u \bmod v) = hcf(v, u)). 또한 (hcf(u, v) = hcf(v, u))이므로 (hcf(u, v) = hcf(v, u \bmod v)).
-
(u \geq v)인 경우: (u = qv + r) (단, (q \in \mathbb{N}^*, r \in \mathbb{N}, r < v))로 나타낼 수 있습니다. 모든 공약수 (d)에 대해 (d \mid u = (qv + r))이고, 따라서 (d \mid r)입니다. 즉, (d)는 (v)와 (r)의 공약수입니다. 반대로, 모든 (v)와 (r)의 공약수 (d')에 대해 (d' \mid qv)이고 (d' \mid r)이므로 (d' \mid (qv + r) = u)입니다. 따라서 (u)와 (v)의 공약수 집합과 (v)와 (r)의 공약수 집합은 동일합니다. 이로부터 (hcf(u, v) = hcf(v, r) = hcf(v, u \bmod v))임을 알 수 있습니다.
따라서 위 식은 항상 성립합니다.
아래는 이를 코드로 구현한 예입니다:
int hcf(int u, int v) {
return v == 0 ? u : hcf(v, u % v);
}
확장 유클리드 알고리즘은 (hcf(u, v))를 계산하는 동시에 방정식 (ux + vy = hcf(u, v))의 한 해를 찾습니다. 이를 위해 다음 관계를 이용합니다:
(ux + vy = d) (vx_0 + (u \bmod v)y_0 = d)
여기서 (u \bmod v = u - \lfloor \frac{u}{v} \rfloor v)로 대체할 수 있습니다. 이를 정리하면:
(uy_0 + v(x_0 - \lfloor \frac{u}{v} \rfloor y_0) = d)
따라서 (x = y_0)이고 (y = x_0 - \lfloor \frac{u}{v} \rfloor y_0)로 설정하여 문제를 해결할 수 있습니다. 이를 재귀적으로 적용하면 됩니다.
아래는 확장 유클리드 알고리즘의 구현입니다:
int ex_hcf(int u, int v, int& x, int& y) {
if (v == 0) {
x = 1, y = 0;
return u;
}
int x0, y0, d = ex_hcf(v, u % v, x0, y0);
x = y0, y = x0 - (u / v) * y0;
return d;
}
또는 다른 형태로도 작성할 수 있습니다:
int ex_hcf(int u, int v, int& x, int& y) {
if (v == 0) {
x = 1, y = 0;
return u;
}
int d = ex_hcf(v, u % v, y, x);
y -= (u / v) * x;
return d;
}
확장 유클리드 알고리즘은 주로 선형 디오판투스 방정식 (ux + vy = c)의 최소 비음수 정수 해를 구하는 데 사용됩니다. 이 과정에서 반드시 (d \mid c)인지 확인해야 합니다. 또한 (c)와 (d)를 (d)로 나눈 값을 사용해야 하며, 그렇지 않으면 결과가 틀릴 수 있습니다.
관련된 문제들은 다음과 같습니다:
- P1516: 청娃의 만남 (확장 유클리드 기본 문제)
- P5656: 선형 디오판투스 방정식 (강화된 데이터 세트)
- P2421: [NOI2002] 황도 야생인 (열거 + 확장 유클리드)