확장 유클리드 호제법(Extended Euclidean Algorithm)

확장 유클리드 호제법

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

\[ ax+by=c \]

만약 $c$가 $a$와 $b$의 최대공약수 $\mathrm{gcd}(a,b)$의 배수가 아니라면 좌변은 최대공약수의 배수이지만 우변은 최대공약수의 배수가 아니므로 모순입니다. 따라서 $c$는 무조건 $a$와 $b$의 최대공약수로 나누어 떨어져야 합니다.

먼저 $c$가 $\mathrm{gcd}(a,b)$인 경우를 생각합시다. $a$를 $b$로 나눈 몫을 $q$, 나머지를 $r$이라 하면 $a=bq+r$이고, 이를 위 방정식에 대입하면

\[ (bq+r)x+by=b(qx+y)+rx=\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r) \]

즉, $a$와 $b$가 주어졌을 때 방정식의 해는 $b$와 $r$이 주어졌을 때 방정식의 해를 이용해서 구할 수 있습니다. 이걸 재귀적으로 계속 반복하면 유클리드 호제법과 마찬가지로 결국에는 $b$가 0이 될 것이고, 그때 $a$는 $\mathrm{gcd}(a,b)$, $x$는 1, $y$는 0이 되겠죠. 이 알고리즘을 확장 유클리드 호제법이라고 합니다.

유클리드 호제법 코드에 조금만 추가하면 쉽게 구할 수 있습니다.

// 최대공약수, x, y를 리턴
tuple<int, int, int> extended_euclidean(int a, int b) {
    if (b == 0)
        return make_tuple(a, 1, 0);
    int g, x, y;
    tie(g, x, y) = extended_euclidean(b, a%b);
    return make_tuple(g, y, x-(a/b)*y);
}

예시로 1914와 899를 넣으면 최대공약수 29와 $1914x+899y=29$를 만족하는 정수 8, -17이 나옵니다. $c$가 $\mathrm{gcd}(a,b)$의 배수일 때에는 확장 유클리드 호제법으로 구한 $x$와 $y$를 정수배하면 됩니다.

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

선형 디오판토스 방정식의 해는 유일하지 않습니다. 두 해 $x_1$, $y_1$과 $x_2$, $y_2$를 생각하면 $ax_1+by_1=ax_2+by_2=c$이므로 $a(x_2-x_1)=b(y_1-y_2)$가 됩니다. $b(y_1-y_2)$이 $a$의 배수가 되려면 $y_1-y_2$가 $a/\mathrm{gcd}(a,b)$의 배수여야 하기 때문에 적당한 정수 $k$에 대해\[ y_2 = y_1-k\frac{a}{\mathrm{gcd}(a,b)} \]마찬가지로\[ x_2 = x_1+k\frac{b}{\mathrm{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)

https://www.acmicpc.net/problem/14565

$n$과 $a$가 주어질 때 법 $n$에 대한 모듈로 연산에서 덧셈과 곱셈에 대한 역원을 구하는 문제입니다. 덧셈에 대한 역원은 당연히 $n-a$고, 곱셈에 대한 역원은 확장 유클리드 호제법으로 구할 수 있습니다. 계산 결과로 나온 최대공약수가 1이 아니면 곱셈에 대한 역원이 없음에 주의합시다.

BOJ 3955:: 캔디 분배

https://www.acmicpc.net/problem/3955

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

\[ X = X_0 + tC, \quad Y = Y_0 – tK \]

가 됩니다($t$는 정수). $X$는 음의 정수, $Y$는 양의 정수이고 문제 조건에서 사탕 봉지가 $10^9$개를 넘지 않는다고 했으므로,

\[ X_0 + tC < 0, \quad 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) \]

이를 만족하는 정수 $t$가 존재하면 $Y$를 출력하면 되고, 아니면 불가능한 경우입니다.

#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

icpc.me/9267

처음에 $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$를 만들 수 있다면

\[6a_0+10b_0=6(a_0+b_0)+4b_0\]

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

\[6a_0+4b_0=2a_0+4(a_0+b_0)\]

이므로 $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, \quad \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:: 해의 개수

icpc.me/11661

제일 먼저 $A$ 또는 $B$가 0인 경우를 처리하고, $C$가 $\gcd(A, B)$의 배수가 아닌 경우도 걸러줍니다. 그 외의 경우엔 방정식 $Ax+By=-C$의 특수해 $x_0$와 $y_0$를 구합니다. 위에서 일반해는

\[ x = x_0+k\frac{B}{\gcd(A, B)} \]

\[ y = y_0-k\frac{A}{\gcd(A, B)} \]

인데 문제에서 $x_1 \le x \le x_2$이고 $y_1 \le y \le y_2$인 해를 구하라고 했으므로

\[ 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 \]

를 풀어 $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;
}