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$.

Thử các nghiệm lân cận. Hàm ext như trê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;
#define 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';
}

ChạyInput35 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)$.

Khi cần nghịch đảo của cả dãy $1, 2, \dots, n$ theo modulo nguyên tố $p$, có cách nhanh hơn cả hai. Viết $p = \lfloor p/i \rfloor \cdot i + (p \bmod i)$, lấy theo modulo $p$ rồi nhân hai vế với $i^{-1} (p \bmod i)^{-1}$:

mà $p \bmod i < i$ đã có nghịch đảo từ trước, nên mỗi số chỉ tốn một phép nhân:

inv[1] = 1;
for (ll i = 2; i <= n; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;

Bảng truy hồi nhanh nhất. Lạ hơn là Euclid mở rộng chậm gấp đôi lũy thừa: nó chia cho số thay đổi ở mỗi bước, còn lũy thừa chỉ chia cho hằng MOD (bài 08). Modulo nguyên tố thì cứ dùng lũy thừa; Euclid mở rộng để dành cho modulo hợp số.

Đồ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;
#define 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';
    }
}

ChạyInput3
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;
#define 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';
    }
}

ChạyInput3
10 4 3
6 1 4
7 0 3

Output2
-1
0

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

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;
#define 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';
}

ChạyInput6 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;
#define 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';
        }
    }
}

ChạyInput4
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))$.