확장 유클리드 알고리즘(ExGCD)의 원리와 활용

베주 항등식 (Bézout's Identity)

두 정수 \(a\)와 \(b\)의 최대공약수를 \(d = \gcd(a, b)\)라고 할 때, 다음 방정식을 만족하는 정수 \(x\)와 \(y\)가 반드시 존재합니다.

\[ax + by = d\]

더 일반적으로 방정식 \(ax + by = c\)를 풀고자 할 때, \(c\)가 \(d\)의 배수가 아니라면 이 방정식은 정수 해를 가질 수 없습니다.

확장 유클리드 알고리즘의 유도

유클리드 호제법을 통해 \(\gcd(a, b)\)를 구하는 과정은 잘 알려져 있습니다. 베주 항등식과 결합하여 생각해보면, \(bx + (a \bmod b)y = d\)라는 방정식은 원래의 방정식과 동일한 해의 구조를 가집니다.

호제법의 마지막 단계인 \(b = 0\)인 경우를 살펴봅시다. 이때 방정식은 \(ax = d\)가 되며, \(a\)는 곧 \(d\)이므로 \(x = 1\), \(y = 0\) (또는 임의의 정수)이 해가 됩니다.

이제 재귀적으로 한 단계씩 올라가며 해를 복원하는 과정을 고려해 봅시다. \(a \bmod b\)는 \(a - \lfloor \frac{a}{b} \rfloor \times b\)로 표현할 수 있으므로, 하위 단계의 방정식은 다음과 같이 변형됩니다.

\[bx + \left(a - \left\lfloor \frac{a}{b} \right\rfloor \times b\right)y = d\]

이를 \(a\)와 \(b\)에 대해 다시 정리하면 다음과 같은 형태가 됩니다.

\[ay + b\left(x - \left\lfloor \frac{a}{b} \right\rfloor y\right) = d\]

하위 단계에서 구한 해를 \((x', y')\)라고 하면, 상위 단계의 해 \((x, y)\)는 다음과 같은 관계를 가집니다.

\[x = y', \quad y = x' - \left\lfloor \frac{a}{b} \right\rfloor y'\]

이를 구현하면 다음과 같습니다.

long long ext_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long next_x, next_y;
    long long g = ext_gcd(b, a % b, next_x, next_y);
    x = next_y;
    y = next_x - (a / b) * next_y;
    return g;
}

일반해(General Solution) 도출

위 알고리즘을 통해 구한 \((x_0, y_0)\)는 방정식 \(ax + by = c\)의 특수해 중 하나입니다. 모든 해를 구하기 위해 다음을 가정해 봅시다.

\[a(x_0 + p) + b(y_0 + q) = c\]

이미 \(ax_0 + by_0 = c\)가 성립하므로, 위 식에서 이를 빼면 다음을 얻습니다.

\[ap + bq = 0 \implies p = -\frac{b}{d}k, \quad q = \frac{a}{d}k \quad (k \in \mathbb{Z})\]

따라서 방정식의 일반해는 임의의 정수 \(k\)에 대해 다음과 같이 표현됩니다.

\[\begin{cases} x = x_0 + k \cdot \frac{b}{d} \\ y = y_0 - k \cdot \frac{a}{d} \end{cases}\]

조건을 만족하는 해 구하기

\(x\)와 \(y\)가 모두 양의 정수인 해의 범위, 혹은 그러한 해가 존재하지 않을 때 각각의 최소 양의 정수 해를 구하는 방법을 살펴봅시다.

\(x > 0\) 조건에서 \(k > -x_0 \cdot \frac{d}{b}\) 이어야 하므로, \(k\)의 최솟값은 \(\lfloor -x_0 \cdot \frac{d}{b} \rfloor + 1\)이 됩니다.

마찬가지로 \(y > 0\) 조건에서 \(k < y_0 \cdot \frac{d}{a}\) 이어야 하므로, \(k\)의 최댓값은 \(\lceil y_0 \cdot \frac{d}{a} \rceil - 1\)이 됩니다.

이 두 범위 내에서 유효한 \(k\)가 존재하는지 확인하면 조건을 만족하는 해의 존재 여부와 개수를 알 수 있습니다.

void solve_positive_solutions(long long a, long long b, long long c) {
    long long g = std::gcd(a, b);
    if (c % g != 0) {
        std::cout << -1 << "\n";
        return;
    }

    long long x, y;
    ext_gcd(a, b, x, y);
    
    long long multiplier = c / g;
    x *= multiplier;
    y *= multiplier;

    long long step_x = b / g;
    long long step_y = a / g;

    long long k_min = static_cast<long long>(std::floor(-static_cast<double>(x) / step_x)) + 1;
    long long k_max = static_cast<long long>(std::ceil(static_cast<double>(y) / step_y)) - 1;

    long long min_x = x + k_min * step_x;
    long long max_y = y - k_min * step_y;
    long long max_x = x + k_max * step_x;
    long long min_y = y - k_max * step_y;

    if (min_x > 0 && min_y > 0) {
        std::cout << k_max - k_min + 1 << " "
                  << min_x << " " << min_y << " "
                  << max_x << " " << max_y << "\n";
    } else {
        std::cout << min_x << " " << max_y << "\n";
    }
}

태그: 확장 유클리드 알고리즘 베주 항등식 정수론 최대공약수 디오판토스 방정식

10월 19일 17:51에 게시됨