유클리드 알고리즘 및 확장 유클리드 알고리즘

유클리드 알고리즘은 두 정수의 최대 공약수를 구하는 효율적인 방법입니다. 이는 일반적으로 '나머지 연산을 이용한 재귀적 접근'으로 설명됩니다. 이를 수학적으로 표현하면 다음과 같습니다:

[hcf(u, v) = \begin{cases} u, & v = 0 \ hcf(v, u \bmod v), & v \neq 0 \end{cases}]

여기서 (u)와 (v)는 두 정수입니다. 이제 이를 증명해봅시다.

  1. (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)).

  2. (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] 황도 야생인 (열거 + 확장 유클리드)

태그: 유클리드알고리즘 확장유클리드알고리즘 C++

10월 27일 15:54에 게시됨