Thuật toán Euclid mở rộng
Thuật toán Euclid trong bài ƯCLN, BCNN cho biết ƯCLN của a và b. Chỉ cần ghi lại thêm một chút trong lúc chạy, thuật toán còn tìm được hai số nguyên x, y sao cho a × x + b × y = ƯCLN(a, b). Từ đó giải được ba loại bài rất hay gặp trong đề học sinh giỏi:
- Phương trình nghiệm nguyên a × x + b × y = c (đong nước bằng hai bình, trả tiền bằng hai loại tờ, ếch nhảy hai kiểu bước).
- Nghịch đảo modulo khi modulo không phải số nguyên tố. Bài Lũy thừa nhanh dùng định lý Fermat nhỏ, chỉ làm được khi modulo là số nguyên tố.
- Phương trình đồng dư a × x ≡ b (mod m).
Các bạn cần nắm vững bài ƯCLN, BCNN và bài Đồng dư trước khi học bài này.
Định lý Bézout
Phần tiêu đề “Định lý Bézout”Với hai số nguyên dương a, b và g = ƯCLN(a, b), luôn có hai số nguyên x, y (có thể âm) sao cho
a × x + b × y = g
Ví dụ a = 240, b = 46, g = 2: chọn x = -9, y = 47 thì 240 × (-9) + 46 × 47 = -2160 + 2162 = 2.
Ngược lại, a × x + b × y luôn chia hết cho g (vì a và b đều chia hết cho g). Vậy g là số dương nhỏ nhất viết được dưới dạng a × x + b × y.
Ý tưởng của thuật toán
Phần tiêu đề “Ý tưởng của thuật toán”Thuật toán Euclid thay (a, b) bằng (b, a % b) cho tới khi số thứ hai bằng 0. Giả sử đã tìm được x’, y’ cho cặp nhỏ hơn:
b × x’ + (a % b) × y’ = g
Thay a % b = a - (a // b) × b rồi gom lại theo a và b:
a × y’ + b × (x’ - (a // b) × y’) = g
Vậy với cặp (a, b) chỉ cần lấy x = y’ và y = x’ - (a // b) × y’. Khi số thứ hai bằng 0 thì a × 1 + 0 × 0 = a, nên bắt đầu từ x = 1, y = 0 rồi đi ngược lên.
Chạy tay với a = 240, b = 46. Đi xuống (cột a // b), rồi điền x, y từ dưới lên:
| a | b | a // b | x | y |
|---|---|---|---|---|
| 240 | 46 | 5 | -9 | 2 - 5 × (-9) = 47 |
| 46 | 10 | 4 | 2 | -1 - 4 × 2 = -9 |
| 10 | 6 | 1 | -1 | 1 - 1 × (-1) = 2 |
| 6 | 4 | 1 | 1 | 0 - 1 × 1 = -1 |
| 4 | 2 | 2 | 0 | 1 - 2 × 0 = 1 |
| 2 | 0 | 1 | 0 |
Hàng trên cùng: 240 × (-9) + 46 × 47 = 2.
def euclid_mo_rong(a, b): """Trả về (g, x, y) với a*x + b*y = g = ƯCLN(a, b).""" if b == 0: return a, 1, 0 g, x1, y1 = euclid_mo_rong(b, a % b) return g, y1, x1 - (a // b) * y1
print(euclid_mo_rong(240, 46)) # (2, -9, 47)#include <iostream>using namespace std;
// Trả về g = ƯCLN(a, b), đồng thời gán x, y sao cho a*x + b*y = g.long long euclidMoRong(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } long long x1, y1; long long g = euclidMoRong(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return g;}
int main() { long long x, y; long long g = euclidMoRong(240, 46, x, y); cout << g << " " << x << " " << y << endl; // 2 -9 47 return 0;}Số bước giống hệt thuật toán Euclid: với a, b đến 1018 chỉ khoảng 90 bước. Các số x, y
tìm được không vượt quá b và a, nên trong C++ không bị tràn long long.
Phương trình a × x + b × y = c
Phần tiêu đề “Phương trình a × x + b × y = c”Có nghiệm nguyên khi và chỉ khi c chia hết cho g = ƯCLN(a, b).
Khi c chia hết cho g: tìm x0, y0 với a × x0 + b × y0 = g, rồi nhân cả hai vế với c / g, được một nghiệm x0 × (c / g), y0 × (c / g).
Từ một nghiệm (x, y), mọi nghiệm có dạng
(x + k × b / g, y - k × a / g) với k nguyên bất kỳ.
Tăng x thêm b / g thì phải giảm y đi a / g để tổng không đổi. Ví dụ 6x + 9y = 15: g = 3, một nghiệm là (1, 1), các nghiệm khác là (4, -1), (-2, 3), (7, -3)… (x tăng 3, y giảm 2).
Đề thường hỏi một nghiệm cụ thể, ví dụ nghiệm có x nhỏ nhất không âm: lấy x theo modulo b / g (x % (b / g) trong Python luôn không âm) rồi tính lại y = (c - a × x) / b.
Lưu ý về tràn số: x0 × (c / g) có thể rất lớn. Trong C++ nên lấy dư cho b / g trước khi nhân.
Nghịch đảo modulo m bất kỳ
Phần tiêu đề “Nghịch đảo modulo m bất kỳ”Nghịch đảo của a theo modulo m là số x với a × x ≡ 1 (mod m), tức a × x + m × y = 1 với y nào đó. Theo định lý Bézout:
- Có nghịch đảo khi và chỉ khi ƯCLN(a, m) = 1.
- Khi đó chạy Euclid mở rộng với (a, m), lấy x % m.
Ví dụ nghịch đảo của 3 theo modulo 10: Euclid mở rộng cho 3 × (-3) + 10 × 1 = 1, nên nghịch đảo là -3 % 10 = 7. Thử lại: 3 × 7 = 21 ≡ 1 (mod 10). Modulo 10 không phải số nguyên tố nên định lý Fermat nhỏ không dùng được.
Python 3.8 trở lên có sẵn pow(a, -1, m) (báo lỗi ValueError khi không có nghịch đảo), rất
tiện để kiểm tra lại kết quả.
Phương trình đồng dư a × x ≡ b (mod m)
Phần tiêu đề “Phương trình đồng dư a × x ≡ b (mod m)”Phương trình có nghĩa là a × x - b chia hết cho m, tức a × x + m × y = b với y nào đó. Đặt g = ƯCLN(a, m):
- Nếu b không chia hết cho g: vô nghiệm.
- Nếu b chia hết cho g: chia cả a, b, m cho g, rồi x = (b / g) × nghịch đảo của (a / g) theo modulo (m / g). Trong khoảng từ 0 đến m - 1 có đúng g nghiệm, cách nhau m / g.
Ví dụ 6x ≡ 4 (mod 10): g = 2, chia đôi được 3x ≡ 2 (mod 5). Nghịch đảo của 3 theo modulo 5 là 2, nên x ≡ 2 × 2 = 4 (mod 5). Hai nghiệm từ 0 đến 9 là 4 và 9.
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 20 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.
Nhóm 1. Định lý Bézout và phương trình a × x + b × y = c
Phần tiêu đề “Nhóm 1. Định lý Bézout và phương trình a × x + b × y = c”Bài 1. Hệ số Bézout
Phần tiêu đề “Bài 1. Hệ số Bézout”Nhập hai số nguyên dương a, b (a, b ≤ 109). Gọi g = ƯCLN(a, b). In ra g, x, y sao cho a × x + b × y = g và 0 ≤ x nhỏ hơn b / g (cặp x, y như vậy là duy nhất).
Ví dụ: nhập 240 46 thì in ra 2 14 -73.
Kiểm tra: nhập 1000000007 998244353.
Bài 2. Nghịch đảo modulo
Phần tiêu đề “Bài 2. Nghịch đảo modulo”Nhập hai số nguyên dương a, m (1 ≤ a ≤ 1018, 2 ≤ m ≤ 1018). In ra số x từ 0 đến m - 1 sao cho a × x chia cho m dư 1. Nếu không có, in ra -1.
Ví dụ: nhập 3 10 thì in ra 7.
Kiểm tra: nhập 123456789 1000000000000000000.
Bài 3. Có nghiệm nguyên không
Phần tiêu đề “Bài 3. Có nghiệm nguyên không”Nhập ba số nguyên a, b, c (1 ≤ a, b ≤ 109, |c| ≤ 1018). Phương trình a × x + b × y = c có nghiệm nguyên (x, y) không? In ra CÓ hoặc KHÔNG.
Ví dụ: nhập 6 9 15 thì in ra CÓ.
Kiểm tra: nhập 1000000 999998 3.
Bài 4. Một nghiệm của phương trình
Phần tiêu đề “Bài 4. Một nghiệm của phương trình”Nhập ba số nguyên a, b, c (1 ≤ a, b ≤ 109, |c| ≤ 109). Tìm nghiệm nguyên của a × x + b × y = c có x nhỏ nhất không âm, in ra x và y. Nếu vô nghiệm, in ra -1.
Ví dụ: nhập 6 9 15 thì in ra 1 1.
Kiểm tra: nhập 35 47 1000.
Bài 5. Đếm nghiệm không âm
Phần tiêu đề “Bài 5. Đếm nghiệm không âm”Nhập ba số nguyên a, b, c (1 ≤ a, b ≤ 109, 0 ≤ c ≤ 1018). Đếm số cặp số nguyên không âm (x, y) thỏa mãn a × x + b × y = c.
Ví dụ: nhập 2 3 12 thì in ra 3.
Kiểm tra: nhập 7 11 1000000.
Nhóm 2. Nghịch đảo modulo và phương trình đồng dư
Phần tiêu đề “Nhóm 2. Nghịch đảo modulo và phương trình đồng dư”Bài 6. Phép chia theo modulo bất kỳ
Phần tiêu đề “Bài 6. Phép chia theo modulo bất kỳ”Nhập ba số nguyên a, b, m (0 ≤ a ≤ 1018, 1 ≤ b ≤ 1018, 2 ≤ m ≤ 109), biết ƯCLN(b, m) = 1. In ra số x từ 0 đến m - 1 sao cho b × x ≡ a (mod m), tức là “a chia cho b” theo modulo m.
Ví dụ: nhập 10 3 14 thì in ra 8.
Kiểm tra: nhập 999999999999999999 7 1000000000.
Bài 7. Phương trình đồng dư
Phần tiêu đề “Bài 7. Phương trình đồng dư”Nhập ba số nguyên a, b, m (0 ≤ a, b ≤ 1018, 1 ≤ m ≤ 109). In ra số x nhỏ nhất từ 0 đến m - 1 sao cho a × x ≡ b (mod m). Nếu không có, in ra -1.
Ví dụ: nhập 6 4 10 thì in ra 4.
Kiểm tra: nhập 123456 7936 1000000.
Bài 8. Đếm nghiệm đồng dư
Phần tiêu đề “Bài 8. Đếm nghiệm đồng dư”Nhập ba số nguyên a, b, m (0 ≤ a, b ≤ 1018, 1 ≤ m ≤ 1018). Có bao nhiêu số x từ 0 đến m - 1 thỏa mãn a × x ≡ b (mod m)?
Ví dụ: nhập 6 4 10 thì in ra 2.
Kiểm tra: nhập 123456 7936 1000000.
Bài 9. Nghịch đảo của nhiều số
Phần tiêu đề “Bài 9. Nghịch đảo của nhiều số”Dòng đầu là hai số n, m (1 ≤ n ≤ 105, 2 ≤ m ≤ 1018). Dòng thứ hai có n số nguyên dương không quá 1018. Với mỗi số, in ra nghịch đảo của nó theo modulo m (từ 0 đến m - 1), hoặc -1 nếu không có. Các kết quả in trên một dòng, cách nhau một dấu cách.
Ví dụ:
| Nhập | In ra |
|---|---|
4 101 3 4 7 | 1 7 -1 3 |
Kiểm tra: nhập
5 10000000003 7 11 13 1000000001Bài 10. Nghịch đảo của 1 đến n
Phần tiêu đề “Bài 10. Nghịch đảo của 1 đến n”Nhập n và số nguyên tố p (1 ≤ n nhỏ hơn p, n ≤ 106, p ≤ 2 × 109). In ra tổng các nghịch đảo của 1, 2, …, n theo modulo p, chia lấy dư cho p.
Ví dụ: nhập 4 7 thì in ra 5.
Kiểm tra: nhập 1000000 1000000007.
Nhóm 3. Bài toán thực tế
Phần tiêu đề “Nhóm 3. Bài toán thực tế”Bài 11. Đong nước bằng hai bình
Phần tiêu đề “Bài 11. Đong nước bằng hai bình”Có hai bình không vạch chia, dung tích a lít và b lít, và một bể nước. Mỗi thao tác được: đổ đầy một bình từ bể, đổ hết một bình ra ngoài, hoặc rót từ bình này sang bình kia cho tới khi bình kia đầy hoặc bình này hết. Nhập a, b, c (1 ≤ a, b ≤ 109, 0 ≤ c ≤ 109). Có thể làm cho một trong hai bình chứa đúng c lít không? In ra CÓ hoặc KHÔNG.
Ví dụ: nhập 3 5 4 thì in ra CÓ.
Kiểm tra: nhập 21 35 14.
Bài 12. Trả tiền ít tờ nhất
Phần tiêu đề “Bài 12. Trả tiền ít tờ nhất”Có các tờ tiền mệnh giá a đồng và b đồng (mỗi loại có bao nhiêu tờ cũng được). Nhập a, b, c (1 ≤ a, b ≤ 109, 0 ≤ c ≤ 109). Cần trả đúng c đồng (không được trả lại). In ra số tờ ít nhất, hoặc -1 nếu không trả được.
Ví dụ: nhập 2 5 11 thì in ra 4.
Kiểm tra: nhập 7 3 1000000.
Bài 13. Ếch nhảy hai kiểu
Phần tiêu đề “Bài 13. Ếch nhảy hai kiểu”Chú ếch đứng ở vị trí 0 trên trục số. Mỗi bước, ếch nhảy sang phải đúng a đơn vị hoặc sang trái đúng b đơn vị. Nhập a, b, c (1 ≤ a, b ≤ 106, |c| ≤ 109). In ra số bước ít nhất để ếch tới vị trí c, hoặc -1 nếu không tới được.
Ví dụ: nhập 5 3 1 thì in ra 5.
Kiểm tra: nhập 17 10 3.
Bài 14. Hai tuyến xe buýt
Phần tiêu đề “Bài 14. Hai tuyến xe buýt”Xe tuyến A đến bến vào các phút p, p + a, p + 2a, … Xe tuyến B đến bến vào các phút q, q + b, q + 2b, … Nhập p, a, q, b (0 ≤ p, q ≤ 109, 1 ≤ a, b ≤ 109). In ra phút sớm nhất mà cả hai xe cùng đến bến, hoặc -1 nếu không bao giờ.
Ví dụ: nhập 3 5 2 7 thì in ra 23.
Kiểm tra: nhập 10 6 4 15.
Bài 15. Số tiền lớn nhất không trả được
Phần tiêu đề “Bài 15. Số tiền lớn nhất không trả được”Có các tờ tiền mệnh giá a và b đồng (mỗi loại bao nhiêu tờ cũng được), biết ƯCLN(a, b) = 1 và 2 ≤ a, b ≤ 109. Số tiền lớn nhất không thể trả đúng bằng hai loại tờ này là bao nhiêu?
Ví dụ: nhập 3 5 thì in ra 7.
Kiểm tra: nhập 12 35.
Bài 16. Đếm số tiền trả được
Phần tiêu đề “Bài 16. Đếm số tiền trả được”Có các tờ tiền mệnh giá a và b đồng, biết ƯCLN(a, b) = 1, 1 ≤ a ≤ 106, 1 ≤ b ≤ 109. Nhập a, b, n (n ≤ 1018). Trong các số tiền 1, 2, …, n, có bao nhiêu số trả đúng được bằng hai loại tờ này?
Ví dụ: nhập 3 5 10 thì in ra 6.
Kiểm tra: nhập 7 10 1000.
Nhóm 4. Vận dụng
Phần tiêu đề “Nhóm 4. Vận dụng”Bài 17. Chuyền bóng quanh vòng tròn
Phần tiêu đề “Bài 17. Chuyền bóng quanh vòng tròn”n bạn đứng thành vòng tròn, đánh số 0 đến n - 1 theo chiều kim đồng hồ. Bóng đang ở bạn số s. Mỗi lần, bạn cầm bóng chuyền cho bạn đứng cách mình k vị trí theo chiều kim đồng hồ. Nhập n, k, s, t (1 ≤ n ≤ 109, 0 ≤ k, s, t nhỏ hơn n). Cần ít nhất bao nhiêu lần chuyền để bóng tới bạn số t? In ra -1 nếu không bao giờ tới.
Ví dụ: nhập 10 4 0 6 thì in ra 4.
Kiểm tra: nhập 1000000 360 5 845.
Bài 18. Phương trình ba ẩn
Phần tiêu đề “Bài 18. Phương trình ba ẩn”Nhập bốn số nguyên a, b, c, d (1 ≤ a, b, c ≤ 109, |d| ≤ 1018). Phương trình a × x + b × y + c × z = d có nghiệm nguyên không? In ra CÓ hoặc KHÔNG.
Ví dụ: nhập 6 10 15 1 thì in ra CÓ.
Kiểm tra: nhập 12 18 30 10.
Bài 19. Những vị trí tới được
Phần tiêu đề “Bài 19. Những vị trí tới được”Bắt đầu từ số 0, mỗi bước được cộng hoặc trừ a, hoặc cộng hoặc trừ b. Nhập a, b, L, R (1 ≤ a, b ≤ 109, -1018 ≤ L ≤ R ≤ 1018). Có bao nhiêu số nguyên trong đoạn từ L đến R tới được sau một số bước nào đó?
Ví dụ: nhập 4 6 -5 10 thì in ra 8.
Kiểm tra: nhập 15 21 -1000 1000.
Bài 20. Cân hai đĩa
Phần tiêu đề “Bài 20. Cân hai đĩa”Có các quả cân a gam và b gam (mỗi loại bao nhiêu quả cũng được). Quả cân được đặt ở cả hai đĩa của cân. Nhập a, b, c (1 ≤ a, b ≤ 109, 1 ≤ c ≤ 109). Cần ít nhất bao nhiêu quả cân để cân được một vật nặng đúng c gam? In ra -1 nếu không cân được.
Ví dụ: nhập 3 7 1 thì in ra 3.
Kiểm tra: nhập 11 17 100.
© 2026 Bumbii Academy. Toàn bộ nội dung thuộc bản quyền của Bumbii Academy, nghiêm cấm sao chép dưới mọi hình thức khi chưa được cho phép.