확장 유클리드 호제법

양의 정수 $a$, $b$, $c$가 주어질 때 다음 선형 디오판토스 방정식(linear Diophantine equation)을 만족하는 정수 $x$와 $y$를 구해봅시다.

\begin{equation*} ax + by = c \end{equation*}

만약 $c$가 $a$와 $b$의 최대공약수 $\gcd(a, b)$의 배수가 아니라면 좌변은 최대공약수의 배수인데 우변은 아니므로 모순입니다. 먼저 $c$가 최대공약수인 경우부터 살펴봅시다. $a$를 $b$로 나눈 몫을 $q$, 나머지를 $r$이라 하면 $a=bq+r$이고, 방정식에 대입하면

\[ (bq+r)x + by = \gcd(a,b) \]

또는 유클리드 호제법에 의해 $\gcd(a,b) = \gcd(b,r)$이므로

\[ b(qx+y)+rx = \gcd(b,r) \]

즉, $a$와 $b$가 주어졌을 때 방정식의 해는 $a$ 대신 $b$, $b$ 대신 $r$을 넣어 만든 방정식의 해로부터 역산할 수 있습니다. 이걸 재귀적으로 계속 반복하면 유클리도 호제법과 완전히 동일한 과정을 거쳐 $a$에 $\gcd(a, b)$, $b$에 0이 들어간 방정식에 도달하게 됩니다. 이 알고리즘을 확장 유클리드 호제법(extended Euclidean algorithm)이라고 합니다.


// returns {gcd, x, y}
tuple<int, int, int> extended_euclidean(int a, int b) {
    if (b == 0)
        return {a, 1, 0};
    auto [g, x, y] = extended_euclidean(b, a%b);
    return {g, y, x-(a/b)*y};
}

예를 들어 1914와 899를 넣으면 최대공약수 29와 $1914x+899y=29$를 만족하는 정수 8, -17이 나옵니다.

$c$가 $\gcd(a, b)$의 정수배인 경우 확장 유클리드 호제법으로 구한 값을 똑같이 정수배하면 됩니다.

선형 디오판토스 방정식의 일반해

사실 선형 디오판토스 방정식의 해는 유일하지 않습니다. 확장 유클리드 호제법으로 구한 해를 $x_0$, $y_0$라 하고 일반해를 $x$, $y$라 하면

\begin{gather*} ax + by = ax_0 + by_0 = c \\ a(x - x_0) = b(y_0 - y) \end{gather*}

$a(x - x_0)$가 $b$의 배수가 되려면 $x-x_0$는 $b/\gcd(a,b)$의 배수가 되어야 하기 때문에 적당한 정수 $k$에 대해

\[ x = x_0 + k \frac{b}{\gcd(a,b)} \]

마찬가지로

\[ y = y_0 - k \frac{a}{\gcd(a,b)} \]

모듈로 연산에서 곱셈에 대한 역원 구하기

법 $m$에 대한 모듈로 연산에서 정수 $a$의 곱셈에 대한 역원 $a^{-1}$은 다음을 만족하는 정수 $x$로 정의합니다.

\[ ax \equiv 1 \pmod m \]

모듈로 연산의 정의에 의해 $ax-1 = -my$를 만족하는 정수 $y$가 존재해야 하고, 다시 말해

\[ ax+my = 1 \]

을 만족하는 정수 $x$, $y$가 존재해야 합니다. 위에서 살펴본대로 $a$와 $m$의 최대공약수가 1(즉, 서로소)일 때에만 곱셈에 대한 역원 $a^{-1}$이 존재합니다.

응용

BOJ 14565:: 역원(Inverse)

곱셈에 대한 역원을 구하면 되는 문제입니다.

BOJ 3955:: 캔디 분배

$KX+1=CY$를 만족하는 양의 정수 $X$, $Y$가 존재하는지 판별하는 문제입니다. 다르게 말하자면 $KX+CY=1$을 만족하는 음의 정수 $X$와 양의 정수 $Y$가 존재하는지 판별하는 문제가 됩니다. 일단 $K$와 $C$가 서로소인지 먼저 확인합시다. 그 다음 확장 유클리드 호제법으로 특수해 $X_0$, $Y_0$를 구하면 일반해는

\[ X = X_0 + tC, \qquad Y = Y_0 - tK \]

입니다. ($t$는 정수) $X$는 음의 정수, $Y$는 양의 정수이고 문제 조건에서 사탕 봉지가 10⁹개를 넘지 않는다고 했으므로 다음을 만족하는 정수 $t$가 존재하는지 판별하면 됩니다.

\begin{gather*} X_0 + tC < 0, \qquad 0 < Y_0 - tK \le 10^9 \\ \therefore \frac{Y_0 - 10^9}{K} \le t < \min\left(-\frac{X_0}{C}, \frac{Y_0}{K}\right) \end{gather*}


#include<bits/stdc++.h>

using namespace std;
using ll = long long;

tuple<ll, ll, ll> extended_euclidean(ll a, ll b) {
    if (b == 0)
        return make_tuple(a, 1, 0);
    ll g, x, y;
    tie(g, x, y) = extended_euclidean(b, a%b);
    return make_tuple(g, y, x-(a/b)*y);
}

ll ceil(ll a, ll b) {
    if (a >= 0)
        return (a + b - 1) / b;
    return a / b;
}

void solve(ll k, ll c) {
    ll g, x0, y0;
    tie(g, x0, y0) = extended_euclidean(k, c);

    if (g != 1) {
        cout << "IMPOSSIBLE\n";
        return;
    }

    ll t = min(ceil(-x0, c), ceil(y0, k)) - 1;
    if (y0 - 1e9 > k*t) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    cout << y0 - t * k << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        ll k, c;
        cin >> k >> c;
        solve(k, c);
    }

    return 0;
}

BOJ 9267:: A+B

처음에 $a$와 $b$의 값을 각각 $a_0$, $b_0$라 하면 두 명령을 적용해서 만들 수 있는 수는 모두 $a_0x+b_0y$ 꼴로 나타낼 수 있습니다. ($x$와 $y$는 음이 아닌 정수) 그런데 $s$가 저 꼴이라고 항상 되는 게 아닙니다. 예를 들어 $6a_0+10b_0$ 같은 수는 두 명령을 어떻게 써도 만들 수 없습니다. 그렇다면 $x$와 $y$는 어떤 조건을 만족해야 할까요?

처음에 $a_0$와 $b_0$로 시작해서 만들 수 있는 수들은 모두 처음에 $a_0+b_0$와 $b_0$로 시작해서 만들 수 있거나 $a_0$와 $a_0+b_0$로 시작해서 만들 수 있는 수입니다. 만약 $a_0$와 $b_0$에서 시작해서 $6a_0+10b_0$를 만들 수 있다면

\begin{equation*} 6a_0 + 10b_0 = 6(a_0 + b_0) + 4b_0 \end{equation*}

이므로 $a_0+b_0$와 $b_0$에서 시작해서 $6(a_0+b_0)+4b_0$를 만들 수 있다는 것이고, 같은 명령들을 $a_0$와 $b_0$에서 시작하는 경우에 적용하면 $6a_0+4b_0$를 만들 수 있다는 뜻이 됩니다. 그럼 다시

\begin{equation*} 6a_0+4b_0=2a_0+4(a_0+b_0) \end{equation*}

이므로 $a_0$와 $a_0+b_0$에서 시작해 $2a_0+4(a_0+b_0)$를 만들 수 있고, 똑같이 $a_0$와 $b_0$에서 시작해 $2a_0+4b_0$를 만들 수 있습니다. 계속해서 한 번 더 적용하면 $2a_0+2b_0$를 만들 수 있고, 또 적용하면 $2a_0$(또는 $2b_0$)를 만들 수 있다는 결론이 나오는데 이건 불가능하죠. 따라서 $6a_0+10b_0$는 만들 수 없음이 증명됩니다. 아하! 유클리드 호제법이네요.

$a_0x+b_0y$를 만들 수 있으면 위 과정에 의해 $\gcd(x,y)a_0$나 $\gcd(x,y)b_0$ 또한 만들 수 있어야 하므로 $\gcd(x,y)=1$이어야 합니다. 결론적으로 이 문제는

\[ a_0x + b_0y = s, \qquad \gcd(x, y) = 1 \]

을 만족하는 음이 아닌 정수 $x$, $y$가 존재하는지 묻는 문제가 되고, 이는 확장 유클리드 호제법으로 쉽게 풀 수 있습니다.

오버플로 문제가 상당하기 때문에 파이썬으로 짜는 게 여러모로 이롭습니다.


def ext_euc(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = ext_euc(b, a%b)
    return g, y, x-(a//b)*y

def solve(a, b, s):
    if a == 0 and b == 0:
        return s == 0
    if a == 0:
        return s % b == 0
    if b == 0:
        return s % a == 0
    g, x, y = ext_euc(a, b)
    if s % g != 0:
        return False
    x *= s // g
    y *= s // g
    for k in range(-g*x//b+1, g*y//a+1):
        if ext_euc(x + k*b//g, y - k*a//g)[0] == 1:
            return True
    return False

a, b, s = map(int, input().split())
print("YES" if solve(a, b, s) else "NO")

BOJ 11661:: 해의 개수

제일 먼저 $A$ 또는 $B$가 0인 경우를 처리하고, $C$가 $\gcd(A,B)$의 배수가 아닌 경우도 걸러줍니다. 그 외의 경우엔 방정식 $Ax+By=−C$의 특수해 $x_0$와 $y_0$를 구합니다. 문제에서 $x_1\le x\le x_2$이고 $y_1\le y\le y_2$인 해를 구하라고 했으므로

\begin{gather*} x_1 \le x_0 + k\frac{B}{\gcd(A,B)} \le x_2 \\ y_1 \le y_0 - k\frac{A}{\gcd(A,B)} \le y_2 \end{gather*}

를 풀어 $k$에 대한 부등식을 만들면 됩니다. $A$, $B$와 그 최대공약수가 양수냐 음수냐에 따라 부등호 방향이 바뀌기 때문에 경우를 일일이 따져봐야 합니다.


#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using Pint = pair<int, int>;
using Tint = tuple<int, int, int>;

tuple<ll, ll, ll> extended_euclidean(ll a, ll b) {
    if (b == 0)
        return {a, 1LL, 0LL};
    auto [g, x, y] = extended_euclidean(b, a%b);
    return {g, y, x-(a/b)*y};
}

ll floor(ll a, ll b) {
    if (b < 0) {
        a = -a;
        b = -b;
    }
    if (a < 0)
        return -((-a + b - 1) / b);
    return a / b;
}

ll ceil(ll a, ll b) {
    if (b < 0) {
        a = -a;
        b = -b;
    }
    if (a >= 0)
        return (a + b - 1) / b;
    return a / b;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll a, b, c, x1, x2, y1, y2;
    cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2;

    if (x1 > x2 || y1 > y2)
        cout << 0;
    else if (a == 0 && b == 0) {
        if (c == 0)
            cout << (x2 - x1 + 1) * (y2 - y1 + 1);
        else
            cout << 0;
    }
    else if (a == 0 && b != 0) {
        if (c % b != 0 || -c / b < y1 || -c / b > y2)
            cout << 0;
        else
            cout << x2 - x1 + 1;
    }
    else if (a != 0 && b == 0) {
        if (c % a != 0 || -c / a < x1 || -c / a > x2)
            cout << 0;
        else
            cout << y2 - y1 + 1;
    }
    else {
        auto [g, x0, y0] = extended_euclidean(a, b);
        if (c % g != 0)
            cout << 0;
        else {
            x0 *= -c / g;
            y0 *= -c / g;
            ll min1 = ceil(((b / g > 0? x1 : x2) - x0) * g, b);
            ll min2 = ceil((y0 - (a / g > 0? y2 : y1)) * g, a);
            ll max1 = floor(((b / g > 0? x2 : x1) - x0) * g, b);
            ll max2 = floor((y0 - (a / g > 0? y1 : y2)) * g, a);
            ll kmin = max(min1, min2);
            ll kmax = min(max1, max2);
            cout << max(kmax - kmin + 1, 0LL);
        }
    }

    return 0;
}

Algorithm