Extended Euclidean Algorithm

Hệ số Bézout

Giả sử đã có $x_1, y_1$ với $b x_1 + r y_1 = g$, trong đó $r = a \bmod b = a - qb$, $q = \lfloor a/b \rfloor$. Thay $r$ vào: $b x_1 + (a - qb) y_1 = g$, tức $a \cdot y_1 + b \cdot (x_1 - q y_1) = g$. Vậy $x = y_1$, $y = x_1 - q y_1$. Điểm dừng là $b = 0$: $a \cdot 1 + 0 \cdot 0 = a = g$.

ll ext(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1, g = ext(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

Độ sâu đệ quy như Euclid, $O(\log \min(a, b))$. Các hệ số trả về thỏa $|x| \le b/g$ và $|y| \le a/g$, nên không tràn khi $a, b$ vừa ll. Mọi cặp hệ số khác có dạng $(x + k \frac{b}{g},\ y - k \frac{a}{g})$ với $k$ nguyên: hiệu của hai nghiệm phải thỏa $a \Delta x = -b \Delta y$, và $\frac{a}{g}, \frac{b}{g}$ nguyên tố cùng nhau.

Ví dụHệ số Bézout tối ưu

Đề. Cho $a, b \le 10^9$. In hệ số Bézout $x, y$ của $\gcd(a, b)$ với $|x| + |y|$ nhỏ nhất; hòa thì ưu tiên $x \le y$, rồi $x$ nhỏ hơn.

Lời giải. Euclid mở rộng cho một nghiệm $(x, y)$; mọi nghiệm khác là $(x + k \frac{b}{g},\ y - k \frac{a}{g})$. Nghiệm của Euclid đã có $|x| \le b/g$ và $|y| \le a/g$, nên nghiệm tối ưu nằm trong vài nghiệm lân cận, $k$ từ $-2$ tới $2$.

Bước 1: Euclid mở rộng. Lời gọi con cho $b x_1 + (a \bmod b) y_1 = g$. Thay $a \bmod b = a - \lfloor a/b \rfloor b$ rồi gom theo $a$, $b$ được $x = y_1$, $y = x_1 - \lfloor a/b \rfloor y_1$. Đáy $b = 0$ có $a \cdot 1 + 0 \cdot 0 = a$.

ll ext(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1, g = ext(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

Bước 2: thử các nghiệm lân cận. da, db là bước dời của họ nghiệm. So theo $|x| + |y|$, hòa thì so cặp (x > y, x): ưu tiên $x \le y$ trước, $x$ nhỏ sau.

for (ll k = -2; k <= 2; k++) {
    ll cx = x + k * da, cy = y - k * db;
    ll s1 = llabs(cx) + llabs(cy), s2 = llabs(bx) + llabs(by);
    if (s1 < s2 || (s1 == s2 && make_pair(cx > cy, cx) < make_pair(bx > by, bx))) bx = cx, by = cy;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1, g = ext(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll a, b, x, y;
    cin >> a >> b;
    ll g = ext(a, b, x, y), da = b / g, db = a / g;
    ll bx = x, by = y;
    for (ll k = -2; k <= 2; k++) {
        ll cx = x + k * da, cy = y - k * db;
        ll s1 = llabs(cx) + llabs(cy), s2 = llabs(bx) + llabs(by);
        if (s1 < s2 || (s1 == s2 && make_pair(cx > cy, cx) < make_pair(bx > by, bx))) bx = cx, by = cy;
    }
    cout << bx << ' ' << by << '\n';
}

Input35 15

Output1 -2

$O(\log \min(a, b))$.

Nghịch đảo modulo

Nghịch đảo của $a$ modulo $m$ là $x$ với $ax \equiv 1 \pmod m$, tức $ax + my = 1$ có nghiệm: tồn tại khi và chỉ khi $\gcd(a, m) = 1$, và khi đó Euclid mở rộng cho $x$ ngay. Đưa về $[0, m)$ bằng (x % m + m) % m. Khác với lũy thừa $a^{m-2}$ (định lý Fermat), cách này đúng với mọi modulo, kể cả hợp số, và chỉ tốn $O(\log m)$.

Ví dụNghịch đảo dương nhỏ nhất

Đề. Cho $a, b \le 2 \cdot 10^9$ nguyên tố cùng nhau. In số nguyên dương nhỏ nhất $x$ với $ax \equiv 1 \pmod b$.

Lời giải. Euclid mở rộng cho $ax + by = 1$, tức $ax \equiv 1 \pmod b$. (x % b + b) % b đưa $x$ về $[0, b)$; vì $\gcd(a, b) = 1$ và $b \ge 2$, nghịch đảo không thể bằng 0, nên đây là nghiệm dương nhỏ nhất. Hàm ext như ví dụ trước.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1, g = ext(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll a, b, x, y;
    cin >> a >> b;
    ext(a, b, x, y);
    cout << (x % b + b) % b << '\n';
}

Input3 11

Output4

$O(\log b)$.

Đồng dư tuyến tính

Đồng dư $ax \equiv b \pmod m$ là phương trình $ax - my = b$. Gọi $g = \gcd(a, m)$: vế trái luôn chia hết cho $g$, nên vô nghiệm nếu $g \nmid b$. Ngược lại chia cả ba số cho $g$: $a' x \equiv b' \pmod{m'}$ với $\gcd(a', m') = 1$, nghiệm duy nhất theo modulo $m'$ là $x \equiv b' \cdot (a')^{-1}$. Theo modulo $m$ ban đầu có đúng $g$ nghiệm, cách nhau $m'$. Phép nhân $b' \cdot (a')^{-1}$ có thể tới $4 \cdot 10^{18}$, nên lấy dư trước khi nhân hoặc dùng __int128.

Ví dụĐồng dư tuyến tính

Đề. $T \le 10^5$ bộ $a, b, m \le 2 \cdot 10^9$. Với mỗi bộ in một nghiệm của $ax \equiv b \pmod m$, hoặc impossible.

Lời giải. Với $g = \gcd(a, m)$: $g \nmid b$ thì vô nghiệm. Ngược lại chia cả ba cho $g$, được $a' x \equiv b' \pmod{m'}$ với $a'$ nguyên tố cùng nhau với $m'$, nên $x = a'^{-1} b' \bmod m'$. Nghiệm này nằm trong $[0, m')$, nhỏ nhất; các nghiệm khác hơn nó một bội của $m'$.

Bước 1: nghịch đảo. ext(a, m, x, y) cho $ax + my = g$; chia cho $g$ thấy $x$ chính là nghịch đảo của $a/g$ theo mô-đun $m/g$.

ll g = ext(a, m, x, y);
if (b % g) {
    cout << "impossible\n";
    continue;
}

Bước 2: nhân. Hai thừa số dưới $m'$ (tới $2 \cdot 10^9$), tích tới $4 \cdot 10^{18}$, sát giới hạn long long, nên ép sang __int128 cho chắc.

ll mm = m / g;
ll r = (__int128)(x % mm + mm) % mm * (b / g % mm) % mm;

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1, g = ext(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    while (T--) {
        ll a, b, m, x, y;
        cin >> a >> b >> m;
        ll g = ext(a, m, x, y);
        if (b % g) {
            cout << "impossible\n";
            continue;
        }
        ll mm = m / g;
        ll r = (__int128)(x % mm + mm) % mm * (b / g % mm) % mm;
        cout << r << '\n';
    }
}

Input3
4 2 6
4 3 6
7 5 9

Output2
impossible
2

Mỗi bộ $O(\log m)$.

Ví dụĐường đến ngai vàng

Đề. Vòng tròn $N \le 10^9$ vị trí, đang ở $S$, mỗi bước tiến $K$. In số bước nhỏ nhất (kể cả 0) để tới vị trí 0, hoặc $-1$.

Lời giải. Sau $t$ bước đang ở $(S + tK) \bmod N$. Cần $S + tK \equiv 0 \pmod N$, tức $Kt \equiv N - S \pmod N$: đồng dư tuyến tính của ví dụ trước với $c = N - S$. Nghiệm nhỏ nhất không âm là đáp án, vì mọi nghiệm khác hơn nó một bội của $N/g$.

Bước 1: giải đồng dư. Ở đây $m' = N/g \le 10^9$, tích hai số dưới $10^9$ vừa long long, không cần __int128.

ll g = ext(k, n, x, y), c = n - s;
if (c % g) {
    cout << -1 << '\n';
    continue;
}
ll mm = n / g;
cout << (x % mm + mm) % mm * (c / g % mm) % mm << '\n';

$S = 0$ cho $c = N$, chia hết cho $g$ và $c/g \bmod m' = 0$, nên in 0 đúng như mong muốn.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1, g = ext(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    while (T--) {
        ll n, s, k, x, y;
        cin >> n >> s >> k;
        ll g = ext(k, n, x, y), c = n - s;
        if (c % g) {
            cout << -1 << '\n';
            continue;
        }
        ll mm = n / g;
        cout << (x % mm + mm) % mm * (c / g % mm) % mm << '\n';
    }
}

Input3
10 4 3
6 1 4
7 0 3

Output2
-1
0

Mỗi bộ $O(\log N)$.

Phương trình $ax + by = c$ và họ nghiệm

Phương trình có nghiệm nguyên khi và chỉ khi $g = \gcd(a, b)$ chia hết $c$. Khi đó nhân hệ số Bézout với $c/g$ được một nghiệm $(x_0, y_0)$, và mọi nghiệm là

Khi $a, b > 0$, $x$ tăng thì $y$ giảm. Muốn nghiệm có $x$ dương nhỏ nhất: lấy $x_0$ modulo $b/g$ rồi đưa về $[1, b/g]$, tính $y$ từ phương trình. Nếu $y$ khi đó vẫn dương thì có nghiệm dương, và số nghiệm dương là số bước $a/g$ còn trừ được từ $y$ mà vẫn dương. Với hệ số âm, đổi dấu ẩn tương ứng rồi giải với giá trị tuyệt đối.

Ví dụĐiểm nguyên trên đường thẳng

Đề. Tìm một điểm nguyên trên đường $Ax + By + C = 0$ với $|A|, |B|, |C| \le 2 \cdot 10^9$, hoặc in $-1$.

Lời giải. Cần $Ax + By = -C$. Giải với giá trị tuyệt đối để ext chạy trên số không âm: $|A| x' + |B| y' = g$. Nếu $g \nmid C$ thì vô nghiệm.

Bước 1: nhân và đổi dấu. Nhân hai hệ số với $-C/g$ được một nghiệm của $|A| x + |B| y = -C$; đổi dấu $x$ khi $A < 0$, $y$ khi $B < 0$ để về đúng phương trình gốc. $|x'| \le |B|/g$, nhân với $|C|/g \le 2 \cdot 10^9$, tích dưới $4 \cdot 10^{18}$, vừa long long.

x *= -C / g;
y *= -C / g;
if (A < 0) x = -x;
if (B < 0) y = -y;

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1, g = ext(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll A, B, C, x, y;
    cin >> A >> B >> C;
    ll g = ext(llabs(A), llabs(B), x, y);
    if (C % g) {
        cout << -1 << '\n';
        return 0;
    }
    x *= -C / g;
    y *= -C / g;
    if (A < 0) x = -x;
    if (B < 0) y = -y;
    cout << x << ' ' << y << '\n';
}

Input6 9 -3

Output-1 1

$O(\log \min(|A|, |B|))$.

Ví dụMẫu Phương Trình Nghiệm Nguyên

Đề. $T \le 2 \cdot 10^5$ phương trình $ax + by = c$ với $a, b, c \le 10^9$. Không có nghiệm nguyên thì in $-1$; có nghiệm nhưng không có nghiệm dương thì in $x$ dương nhỏ nhất và $y$ dương nhỏ nhất (có thể từ hai nghiệm khác nhau); có nghiệm dương thì in số nghiệm dương, $x$ nhỏ nhất, $y$ nhỏ nhất, $x$ lớn nhất, $y$ lớn nhất.

Lời giải. Đặt $p = b/g$, $q = a/g$: mỗi bước tăng $x$ thêm $p$ thì $y$ giảm $q$. Lấy nghiệm có $x$ dương nhỏ nhất; ứng với nó $y$ lớn nhất. Từ đó đếm được còn bao nhiêu bước mà $y$ vẫn dương.

Bước 1: $x$ dương nhỏ nhất. Nhân $x_0$ với $c/g$ theo mô-đun $p$, rồi đưa về $[1, p]$. Tích tới $10^{18}$, vẫn vừa long long.

ll p = b / g, q = a / g;
ll x = (x0 % p) * (c / g % p) % p;
x = (x % p + p) % p;
if (!x) x = p;
ll y = (c - a * x) / b;

(c - a * x) / b chia hết vì $(x, y)$ thuộc họ nghiệm.

Bước 2: có nghiệm dương. $y \ge 1$ thì số nghiệm dương là số lần còn giảm $y$ đi $q$ mà vẫn $\ge 1$, cộng chính nghiệm hiện tại: $\lfloor (y - 1)/q \rfloor + 1$. Nghiệm cuối cho $y$ nhỏ nhất và $x$ lớn nhất.

ll cnt = (y - 1) / q + 1;
cout << cnt << ' ' << x << ' ' << y - (cnt - 1) * q << ' ' << x + (cnt - 1) * p << ' ' << y << '\n';

Bước 3: không có nghiệm dương. Không nghiệm nào cả hai cùng dương; $y$ dương nhỏ nhất (của một nghiệm khác) là $y$ đưa về $[1, q]$.

ll ym = (y % q + q) % q;
if (!ym) ym = q;
cout << x << ' ' << ym << '\n';

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1, g = ext(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    while (T--) {
        ll a, b, c, x0, y0;
        cin >> a >> b >> c;
        ll g = ext(a, b, x0, y0);
        if (c % g) {
            cout << -1 << '\n';
            continue;
        }
        ll p = b / g, q = a / g;
        ll x = (x0 % p) * (c / g % p) % p;
        x = (x % p + p) % p;
        if (!x) x = p;
        ll y = (c - a * x) / b;
        if (y >= 1) {
            ll cnt = (y - 1) / q + 1;
            cout << cnt << ' ' << x << ' ' << y - (cnt - 1) * q << ' ' << x + (cnt - 1) * p << ' ' << y << '\n';
        } else {
            ll ym = (y % q + q) % q;
            if (!ym) ym = q;
            cout << x << ' ' << ym << '\n';
        }
    }
}

Input4
2 3 12
4 6 5
4 6 20
3 5 18

Output1 3 2 3 2
-1
1 2 2 2 2
1 1 3 1 3

Mỗi phương trình $O(\log \min(a, b))$.