Thuật toán Euclid mở rộng

Thuật toán Euclid tìm ước chung lớn nhất $gcd(a,b)$ chỉ trong $O(\log min(a,b))$ phép chia, thay vì thử mọi ước trong $O(min(a,b))$. Bản mở rộng của nó còn trả về hai số nguyên $x,y$ thỏa $ax+by=gcd(a,b)$. Từ một cặp $(x,y)$ đó ta giải được cả một họ bài toán: nghịch đảo modulo khi modulo không nguyên tố, phương trình nghiệm nguyên $ax+by=c$ (đếm nghiệm, tìm nghiệm không âm nhỏ nhất), phương trình đồng dư $ax\equiv c\left(\mathrm{mod}m\right)$ và định lý số dư Trung Hoa (CRT) cho hai modulo bất kỳ.

Ý tưởng / Trực giác

Euclid: vì sao $gcd(a,b)=gcd(b,amodb)$

Viết $a=qb+r$ với $r=amodb$. Số $d$ nào chia hết cả $a$ và $b$ thì chia hết $r=a-qb$; ngược lại $d$ chia hết $b$ và $r$ thì chia hết $a=qb+r$. Vậy hai cặp $(a,b)$ và $(b,r)$ có cùng tập ước chung, nên cùng ước chung lớn nhất. Lặp lại đến khi số thứ hai bằng $0$: $gcd(g,0)=g$.

Vì sao chỉ cần $O(\log )$ bước

Xét cặp $(a,b)$ với $a\ge b$. Sau hai bước, số lớn $a$ bị thay bằng $amodb$, và số này luôn nhỏ hơn $a/2$:

• nếu $b\le a/2$ thì $amodb<b\le a/2$;
• nếu $b>a/2$ thì $amodb=a-b<a/2$.

Cứ hai bước số lớn giảm ít nhất một nửa, nên số bước không quá khoảng $2{\log }_{2}a$. Chặn chính xác hơn là định lý Lamé: trường hợp xấu nhất là hai số Fibonacci liên tiếp (mỗi bước thương đều bằng $1$). Vì $F_{93}>2^{63}$, với mọi cặp số long long thuật toán dừng sau không quá khoảng $90$ phép chia.

Euclid mở rộng: truy ngược nghiệm

Giả sử đã có nghiệm cho cặp nhỏ hơn: $b·x_1+(amodb)·y_1=g$. Thay $amodb=a-\lfloor a/b\rfloor ·b$:

$$b{x}_1+(a-\lfloor \frac{a}{b}\rfloor b)y_1=g⟹a·\underset{x}{\underbrace{y_1}}+b·\underset{y}{\underbrace{(x_1-\lfloor \frac{a}{b}\rfloor y_1)}}=g.$$

Đáy đệ quy là $(g,0)$ với nghiệm hiển nhiên $x=1,y=0$. Mỗi tầng chỉ tốn $O(1)$, nên toàn bộ vẫn $O(\log )$. Ngoài ra, với $a,b>0$, các hệ số trả về luôn nhỏ: $|x|\le b/g$ và $|y|\le a/g$, không bao giờ tràn long long.

Bản lặp dựa trên một bất biến: luôn giữ hai "dòng" $(r,x,y)$ thỏa $a_{0}x+b_{0}y=r$, bắt đầu từ $(a_0,1,0)$ và $(b_0,0,1)$. Mỗi bước lấy dòng trên trừ $q$ lần dòng dưới (đúng phép chia của Euclid trên cột $r$); vì phép trừ tuyến tính nên bất biến vẫn đúng. Khi cột $r$ về $0$, dòng còn lại cho $r=g$ cùng $x,y$ cần tìm.

Định lý Bézout

Với $a,b$ không đồng thời bằng $0$, tập giá trị $\{ax+by:x,y\in \mathbb{Z}\}$ đúng bằng tập mọi bội của $g=gcd(a,b)$.

Một chiều hiển nhiên: $g\mid a$ và $g\mid b$ nên $g\mid ax+by$. Chiều còn lại: Euclid mở rộng tạo ra $g$ nên nhân $x,y$ với $k$ là tạo được $kg$. Hệ quả dùng liên tục:

• $ax+by=c$ có nghiệm nguyên khi và chỉ khi $g\mid c$.
• $a$ có nghịch đảo modulo $m$ khi và chỉ khi $gcd(a,m)=1$: khi đó $ax+my=1$ cho $ax\equiv 1\left(\mathrm{mod}m\right)$, tức $x=a^{-1}$.
• Với hai bước nhảy $+a$ và $-b$, các vị trí đạt được (nếu không bị giới hạn biên) là đúng các bội của $gcd(a,b)$.

Họ nghiệm tổng quát của $ax+by=c$

Nếu $(x_0,y_0)$ là một nghiệm thì mọi nghiệm có dạng

$$x=x_0+k·\frac{b}{g},y=y_0-k·\frac{a}{g},k\in \mathbb{Z}.$$

Lý do: từ $a(x-x_0)=-b(y-y_0)$, chia hai vế cho $g$ được $\frac{a}{g}(x-x_0)=-\frac{b}{g}(y-y_0)$. Vì $\frac{a}{g}$ và $\frac{b}{g}$ nguyên tố cùng nhau nên $\frac{b}{g}\mid x-x_0$. Nói cách khác: các nghiệm nằm cách đều nhau, $x$ nhảy bước $b/g$ còn $y$ nhảy ngược bước $a/g$. Mọi câu hỏi "nghiệm trong khoảng", "nghiệm không âm nhỏ nhất" đều quy về chọn $k$.

Phương trình đồng dư và CRT

• $ax\equiv c\left(\mathrm{mod}m\right)$ tương đương $ax+my=c$. Có nghiệm khi $g=gcd(a,m)\mid c$, và khi đó có đúng $g$ nghiệm trong $[0,m)$, cách đều nhau $m/g$.
• Hệ $x\equiv r_1\left(\mathrm{mod}{m}_1\right)$, $x\equiv r_2\left(\mathrm{mod}{m}_2\right)$: đặt $x=r_1+m_{1}t$, điều kiện thứ hai thành $m_{1}t\equiv r_2-r_1\left(\mathrm{mod}{m}_2\right)$, chính là một phương trình đồng dư. Có nghiệm khi $g=gcd(m_1,m_2)\mid r_2-r_1$, và nghiệm duy nhất theo modulo $lcm(m_1,m_2)$ (không phải $m_1{m}_2$ khi hai modulo không nguyên tố cùng nhau).

Ví dụ chạy tay

Euclid mở rộng với $a=99$, $b=78$

Chiều đi xuống là Euclid thường; chiều đi lên dùng công thức $x=y_1$, $y=x_1-q·y_1$ (với $q=\lfloor a/b\rfloor$ của chính dòng đó):

  đi xuống (Euclid)              đi lên (truy ngược, đọc từ dưới lên)
  a    b    q   a mod b          x      y      kiểm tra a*x + b*y
 ---- ---- ---- -------         ----   ----    -------------------
  99   78    1     21            -11     14     99*(-11) + 78*14 = 3
  78   21    3     15              3    -11     78*3   + 21*(-11) = 3
  21   15    1      6             -2      3     21*(-2)+ 15*3     = 3
  15    6    2      3              1     -2     15*1   + 6*(-2)   = 3
   6    3    2      0              0      1      6*0   + 3*1      = 3
   3    0    -      -              1      0      3*1   + 0*0      = 3   <- đáy

Ví dụ dòng $(78,21)$ với $q=3$: dòng dưới cho $(x_1,y_1)=(-2,3)$, nên $x=3$, $y=-2-3·3=-11$. Kết quả: $gcd(99,78)=3=99·(-11)+78·14$.

Phương trình $99x+78y=6000$ với $x,y\ge 0$

$g=3$ và $3\mid 6000$ nên có nghiệm. Nhân nghiệm trên với $6000/3=2000$ được $x_0=-22000$, $y_0=28000$. Bước nhảy: $x$ tăng $b/g=26$, $y$ giảm $a/g=33$. Rút gọn $x_0$ về $[0,26)$: $-22000mod26=22$, kéo theo $y=(6000-99·22)/78=49$. Họ nghiệm trên trục $k$:

 k   :   -1      0      1      2
 x   :   -4     22     48     74        x = 22 + 26k
 y   :   82     49     16    -17        y = 49 - 33k
              [----------]
               x>=0 và y>=0

Có đúng 2 nghiệm không âm: $(22,49)$ và $(48,16)$. Nghiệm có $x$ không âm nhỏ nhất là $(22,49)$; nghiệm có $x+y$ nhỏ nhất là $(48,16)$, vì mỗi bước $k$ tăng $1$ thì $x+y$ thay đổi $26-33=-7$.

CRT với modulo không nguyên tố cùng nhau

Giải $x\equiv 2\left(\mathrm{mod}6\right)$, $x\equiv 8\left(\mathrm{mod}10\right)$:

 gcd(6, 10) = 2,   6*2 + 10*(-1) = 2           -> p = 2
 r2 - r1 = 6 chia hết cho 2                    -> có nghiệm
 cần 6t ≡ 6 (mod 10)  <=>  3t ≡ 3 (mod 5)
 t = ((r2-r1)/g) * p mod (m2/g) = (6/2)*2 mod 5 = 1
 x = 2 + 6*1 = 8,   lcm(6,10) = 30             -> x ≡ 8 (mod 30)

Kiểm tra: $8=6+2$ và $8mod10=8$. Còn hệ $x\equiv 1\left(\mathrm{mod}6\right)$, $x\equiv 2\left(\mathrm{mod}10\right)$ thì vô nghiệm vì $2\nmid 1$ (vế đầu buộc $x$ lẻ, vế sau buộc $x$ chẵn).

Cài đặt

C++

Toàn bộ thư viện dưới đây đã được kiểm thử ngẫu nhiên với bản vét cạn. __int128 dùng ở những chỗ tích hai số cỡ ${10}^{18}$ có thể tràn.

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

// Classic Euclid
ll gcd_iter(ll a, ll b) {
    while (b != 0) {
        ll r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// Recursive extended Euclid: returns g = gcd(a, b) and sets a*x + b*y = g
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = ext_gcd(b, a % b, x1, y1);
    // b*x1 + (a % b)*y1 = g  and  a % b = a - (a / b) * b
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Iterative version, invariants: a0*x + b0*y = a  and  a0*x1 + b0*y1 = b
ll ext_gcd_iter(ll a, ll b, ll &x, ll &y) {
    ll x1 = 0, y1 = 1;
    x = 1; y = 0;
    while (b != 0) {
        ll q = a / b;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a, b) = make_tuple(b, a - q * b);
    }
    return a;
}

// Inverse of a modulo m (m need not be prime); -1 if gcd(a, m) != 1
ll inv_mod(ll a, ll m) {
    ll x, y;
    ll g = ext_gcd(((a % m) + m) % m, m, x, y);
    if (g != 1) return -1;
    return ((x % m) + m) % m;
}

// One solution of a*x + b*y = c (a, b != 0) with 0 <= x < |b|/g; false if none
bool find_any_solution(ll a, ll b, ll c, ll &x, ll &y, ll &g) {
    ll x1, y1;
    g = ext_gcd(llabs(a), llabs(b), x1, y1);
    if (c % g != 0) return false;
    if (a < 0) x1 = -x1;
    ll step = llabs(b) / g;
    // reduce before multiplying: x1 * (c / g) alone may overflow
    lll t = (lll)(x1 % step) * ((c / g) % step) % step;
    x = (ll)((t + step) % step);
    y = (ll)(((lll)c - (lll)a * x) / b);     // exact division
    return true;
}

// Floor / ceil division that are correct for negative numbers
ll floor_div(ll p, ll q) { return p / q - ((p % q != 0) && ((p < 0) != (q < 0))); }
ll ceil_div(ll p, ll q)  { return p / q + ((p % q != 0) && ((p < 0) == (q < 0))); }

// Number of solutions of a*x + b*y = c (a, b != 0) in the given box
ll count_solutions(ll a, ll b, ll c, ll minx, ll maxx, ll miny, ll maxy) {
    ll x0, y0, g;
    if (!find_any_solution(a, b, c, x0, y0, g)) return 0;
    ll dx = b / g, dy = a / g;               // x = x0 + k*dx, y = y0 - k*dy
    ll kl1, kr1, kl2, kr2;
    if (dx > 0) { kl1 = ceil_div(minx - x0, dx); kr1 = floor_div(maxx - x0, dx); }
    else        { kl1 = ceil_div(maxx - x0, dx); kr1 = floor_div(minx - x0, dx); }
    if (dy > 0) { kl2 = ceil_div(y0 - maxy, dy); kr2 = floor_div(y0 - miny, dy); }
    else        { kl2 = ceil_div(y0 - miny, dy); kr2 = floor_div(y0 - maxy, dy); }
    ll lo = max(kl1, kl2), hi = min(kr1, kr2);
    return hi >= lo ? hi - lo + 1 : 0;
}

// a*x = c (mod m): returns g = number of solutions in [0, m) (0 if none);
// solutions are x0, x0 + step, ..., x0 + (g-1)*step
ll solve_congruence(ll a, ll c, ll m, ll &x0, ll &step) {
    a = ((a % m) + m) % m; c = ((c % m) + m) % m;
    ll x, y;
    ll g = ext_gcd(a, m, x, y);
    if (c % g != 0) return 0;
    step = m / g;
    x0 = (ll)((lll)(((x % step) + step) % step) * (c / g) % step);
    return g;
}

// x = r1 (mod m1), x = r2 (mod m2), moduli need not be coprime.
// Returns {r, lcm(m1, m2)} or {-1, -1} if there is no solution.
pair<ll, ll> crt(ll r1, ll m1, ll r2, ll m2) {
    ll p, q;
    ll g = ext_gcd(m1, m2, p, q);            // m1*p + m2*q = g
    if ((r2 - r1) % g != 0) return {-1, -1};
    ll m2g = m2 / g;
    ll t = (ll)((lll)((r2 - r1) / g % m2g) * (p % m2g) % m2g);
    if (t < 0) t += m2g;
    ll lcm = m1 * m2g;                       // assumed to fit in long long
    ll r = (ll)(((lll)r1 + (lll)m1 * t) % lcm);
    if (r < 0) r += lcm;
    return {r, lcm};
}

int main() {
    ll x, y, g;
    g = ext_gcd(99, 78, x, y);
    printf("gcd=%lld x=%lld y=%lld\n", g, x, y);                 // 3 -11 14
    printf("inv(7, 30)=%lld\n", inv_mod(7, 30));                   // 13
    printf("inv(6, 30)=%lld\n", inv_mod(6, 30));                   // -1
    find_any_solution(99, 78, 6000, x, y, g);
    printf("99x+78y=6000: x=%lld y=%lld\n", x, y);                 // 22 49
    printf("non-negative: %lld\n",
           count_solutions(99, 78, 6000, 0, 6000, 0, 6000));       // 2
    ll x0, st;
    printf("6x=4 (mod 10): %lld solutions", solve_congruence(6, 4, 10, x0, st));
    printf(", x0=%lld step=%lld\n", x0, st);                       // 2, 4, 5
    auto [r, l] = crt(2, 6, 8, 10);
    printf("crt: x = %lld (mod %lld)\n", r, l);                    // 8 30
}

Một số ghi chú khi dùng:

• Nghiệm $x$ không âm nhỏ nhất của $ax+by=c$ (với $a,b>0$): find_any_solution đã trả $x\in [0,b/g)$; chỉ cần kiểm tra thêm $y\ge 0$, tức $ax\le c$. Nếu $y<0$ thì không có nghiệm không âm nào, vì tăng $x$ chỉ làm $y$ nhỏ đi.
• Nghiệm không âm có $x+y$ nhỏ nhất: $x+y$ biến thiên tuyến tính theo $k$, nên tối ưu nằm ở một đầu của khoảng $k$ hợp lệ. Với $a\le b$, dồn càng nhiều vào biến đi với hệ số lớn ($y$) càng tốt, tức lấy $x$ nhỏ nhất.
• CRT nhiều phương trình: gộp dần từng cặp (r, m) = crt(r, m, ri, mi), bắt đầu từ (0, 1); dừng ngay khi gặp -1.

Python

Python có số nguyên không giới hạn nên không lo tràn. Từ Python 3.8, pow(a, -1, m) trả nghịch đảo modulo với $m$ bất kỳ (ném ValueError nếu $gcd(a,m)\ne 1$).

def ext_gcd(a, b):
    """Return (g, x, y) with a*x + b*y = g = gcd(a, b)."""
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b:
        q = a // b
        a, b = b, a - q * b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def crt(r1, m1, r2, m2):
    """Solve x = r1 (mod m1), x = r2 (mod m2). Return (r, lcm) or None."""
    g, p, _ = ext_gcd(m1, m2)
    if (r2 - r1) % g:
        return None
    lcm = m1 // g * m2
    t = (r2 - r1) // g * p % (m2 // g)
    return (r1 + m1 * t) % lcm, lcm


print(ext_gcd(99, 78))      # (3, -11, 14)
print(crt(2, 6, 8, 10))     # (8, 30)
print(pow(7, -1, 30))       # 13

Độ phức tạp

Cột bộ nhớ của các hàm dùng ext_gcd là $O(\log )$ vì đó là độ sâu đệ quy (tối đa khoảng $90$ khung, không đáng kể); thay ext_gcd bằng ext_gcd_iter thì mọi hàm đều chỉ tốn $O(1)$ bộ nhớ.

Điểm mạnh nằm ở count_solutions: số nghiệm trong khoảng có thể tới ${10}^{18}$ nhưng ta chỉ tính hai đầu mút của $k$ nên vẫn là $O(\log )$.

⚠️ Lỗi thường gặp

• Tràn số khi nhân nghiệm với $c/g$. $|x|\le b/g$ có thể cỡ ${10}^{18}$, nhân tiếp $c/g$ là tràn cả long long. Triệu chứng: sai ở test lớn dù test nhỏ đúng. Cách tránh: rút gọn $x$ modulo $b/g$ trước khi nhân, và nhân bằng __int128 (như find_any_solution). Trong CRT cũng có hai chỗ như vậy: tích ((r2-r1)/g % m2g) * (p % m2g) có hai thừa số cỡ $m_2/g$, nên có thể tới $(m_2/g{)}^2\approx {10}^{36}$; và phép cộng $r_1+m_{1}t$ có thể vượt $2^{63}$ dù mỗi số hạng đều vừa (vì $t<m_2/g$ nên riêng $m_{1}t<lcm$ luôn vừa long long khi lcm vừa). Hàm crt ở trên tính cả hai bằng __int128.
• Modulo âm trong C++. x % m mang dấu của x, nên -5 % 3 == -2. Nghiệm từ Euclid mở rộng rất hay âm; luôn chuẩn hóa ((x % m) + m) % m trước khi dùng làm đáp án hay chỉ số mảng.
• Quên chia cho $g$. Bước nhảy nghiệm là $b/g$, không phải $b$; modulo sau khi giải $ax\equiv c\left(\mathrm{mod}m\right)$ là $m/g$, không phải $m$; CRT cho nghiệm theo $lcm$, không phải $m_1{m}_2$. Dùng nhầm sẽ bỏ sót nghiệm hoặc đếm sai.
• Dùng nghịch đảo Fermat $a^{m-2}$ khi $m$ không nguyên tố. Công thức đó chỉ đúng với $m$ nguyên tố. Với $m$ hợp số (ví dụ ${10}^9$, $2^{32}$) phải dùng inv_mod và kiểm tra $gcd(a,m)=1$; nếu không thì nghịch đảo không tồn tại, không được trả bừa một số.
• Chia làm tròn sai với số âm. Khi tìm khoảng $k$, phép / của C++ làm tròn về $0$, không phải làm tròn xuống. Triệu chứng: đếm lệch $1$ nghiệm khi $x_0$ âm. Cách tránh: dùng floor_div/ceil_div riêng, và nhớ đảo chiều bất đẳng thức khi bước nhảy âm.
• Áp CRT "nguyên tố cùng nhau" cho modulo bất kỳ. Công thức $x=\sum r_i{M}_i{M}_i^{-1}$ cần các modulo đôi một nguyên tố cùng nhau; với $m_1=6$, $m_2=10$ thì $6^{-1}mod10$ không tồn tại. Phải kiểm tra $g\mid r_2-r_1$ rồi gộp theo $lcm$ như hàm crt ở trên.
• $lcm$ vượt quá ${10}^{18}$ khi gộp nhiều phương trình. Tích các modulo tăng rất nhanh. Nếu đề chỉ hỏi nghiệm nhỏ nhất $\le$ một giới hạn $X$, có thể dừng sớm khi $lcm>X$; nếu cần giá trị chính xác thì dùng số lớn hoặc Python.
• Euclid bằng phép trừ. Viết while (a != b) if (a > b) a -= b; else b -= a; trông giống Euclid nhưng là $O(max(a,b))$: $gcd({10}^{18},1)$ chạy ${10}^{18}$ vòng. Luôn dùng phép chia lấy dư.
• Hệ số âm hoặc bằng $0$. Gọi ext_gcd với số âm có thể trả $g$ âm; gọi với $a=b=0$ thì $g=0$ và mọi phép chia cho $g$ đều lỗi. Hãy đưa về $|a|,|b|$ rồi sửa dấu (như find_any_solution), và xử lý riêng trường hợp một hệ số bằng $0$.

Biến thể / Mở rộng

• Nghịch đảo của cả dãy $1..n$ modulo $p$ nguyên tố tính được trong $O(n)$ bằng truy hồi $\text{inv}[i]=-\lfloor p/i\rfloor ·\text{inv}[pmodi]modp$; bản thân truy hồi này là một bước của Euclid.
• CRT cho modulo hợp số trong tổ hợp: tính $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ theo từng lũy thừa nguyên tố rồi ghép bằng CRT, xem Định lý Lucas.
• Logarithm rời rạc khi $gcd(a,m)\ne 1$: bước rút gọn trước khi chạy Baby-step Giant-step cần giải đồng dư tuyến tính và nghịch đảo modulo hợp số.
• Bài toán đồng xu (Frobenius) hai loại: với $gcd(a,b)=1$, số lớn nhất không biểu diễn được dạng $ax+by$ với $x,y\ge 0$ là $ab-a-b$, và có đúng $\frac{(a-1)(b-1)}{2}$ số như vậy.
• Tổng quan các công cụ số học khác (sàng, lũy thừa nhanh, phân tích thừa số) ở trang Toán học.

Bài tập luyện

Pool hiện chỉ có một bài gắn tag extended_euclid (bài VOI bên dưới), nên phần luyện kỹ thuật chọn các bài mà lời giải thực sự dựa vào Euclid, Bézout, phương trình nghiệm nguyên hoặc CRT.

Luyện kỹ thuật

• Phep Tinh GCD (gcdspell) (Học việc) khởi động: cài Euclid cho $A,B\le {10}^{18}$, chú ý kiểu long long và dùng phép chia lấy dư thay cho phép trừ.
• Hàng rào vô hạn (inffence) (Nâng cao) chia $r,b$ cho $gcd(r,b)$ để hai số nguyên tố cùng nhau, rồi dùng Bézout để thấy tấm đỏ có thể nằm cách tấm xanh đúng $1$ đơn vị (theo độ dài đã rút gọn); từ đó tính số tấm cùng màu liên tiếp nhiều nhất.
• Trò chơi đồng dư (remgm42) (Nâng cao) theo CRT, biết mọi $xmod{c}_i$ tương đương biết $xmodlcm(c_i)$ và không hơn; câu hỏi quy về kiểm tra $k\mid lcm$ mà không để lcm tràn số.
• Ngày may mắn (luckydays) (Kỳ cựu) theo Bézout, độ lệch giữa đầu hai đoạn may mắn chỉ có thể thay đổi theo bội của $gcd(t_a,t_b)$; thử hai độ lệch gần $0$ nhất rồi lấy giao đoạn.
• Phân số (fractions) (Kỳ cựu) tách $n=p^k·q$ với hai thừa số nguyên tố cùng nhau, rồi giải phương trình nghiệm nguyên $aq+b{p}^k=n-1$ với ràng buộc $1\le a<p^k$, $1\le b<q$.

Đề VOI

• Sản xuất gỗ (voi24_wpro) (Kỳ cựu) VOI 2024: sau khi đưa về quy hoạch động trên các mối nối ban đầu, bài toán con là tìm nghiệm không âm của $L_{1}a+L_{2}b=\ell$ sao cho $a+b$ nhỏ nhất; để ý số lần phải giải bài toán con này trước khi chọn cách cài đặt.