Ước chung lớn nhất, bội chung nhỏ nhất - thuật toán Euclid
Ước chung lớn nhất (ƯCLN, tiếng Anh là gcd - greatest common divisor) và bội chung nhỏ nhất (BCNN, tiếng Anh là lcm - least common multiple) xuất hiện trong rất nhiều bài: rút gọn phân số, chia nhóm đều nhau, cắt hình vuông, đèn nhấp nháy cùng lúc… Thuật toán Euclid là một trong những thuật toán cổ nhất còn được dùng hằng ngày: tìm ƯCLN của hai số đến 1018 chỉ trong vài chục bước.
Ước chung lớn nhất là gì?
Phần tiêu đề “Ước chung lớn nhất là gì?”Các ước của 12 là 1, 2, 3, 4, 6, 12. Các ước của 18 là 1, 2, 3, 6, 9, 18. Các ước chung là 1, 2, 3, 6, và ước chung lớn nhất là 6.
Cách liệt kê ước như bài Ước và bội cần duyệt đến , tức 109 bước với a = 1018, quá chậm. Thuật toán Euclid nhanh hơn rất nhiều.
Ý tưởng của thuật toán Euclid
Phần tiêu đề “Ý tưởng của thuật toán Euclid”Nguyên tắc: ƯCLN của a và b bằng ƯCLN của b và r, với r là số dư khi chia a cho b:
- ƯCLN(a, b) = ƯCLN(b, r), với r = a % b
Lặp lại cho tới khi số dư bằng 0. Khi đó số chia cuối cùng chính là ƯCLN.
Các bước (với a ≥ b > 0):
- Chia a cho b, được a = b × q + r (q là thương, r là số dư).
- Nếu r = 0 thì ƯCLN(a, b) = b, dừng.
- Nếu r ≠ 0 thì gán a = b, b = r rồi quay lại bước 1.
Ví dụ: tìm ƯCLN(48, 18).
- 48 = 18 × 2 + 12 (số dư 12)
- 18 = 12 × 1 + 6 (số dư 6)
- 12 = 6 × 2 + 0 (số dư 0)
Số dư đã bằng 0, số chia cuối cùng là 6, nên ƯCLN(48, 18) = 6.
Vì sao ƯCLN(a, b) = ƯCLN(b, r)? Nếu a và b cùng chia hết cho d thì a - b cũng chia hết cho d. Ngược lại, b và a - b cùng chia hết cho d thì a = b + (a - b) cũng chia hết cho d. Vậy thay a bằng a - b, các ước chung không đổi, nên ƯCLN không đổi. Ví dụ 48, 18 và 30, 18 (48 - 18 = 30) đều có các ước chung 1, 2, 3, 6.
Trừ tiếp: 48 - 18 = 30, 30 - 18 = 12, và 12 nhỏ hơn 18 nên dừng. Số còn lại 12 chính là số dư trong 48 = 18 × 2 + 12. Vậy ƯCLN(48, 18) = ƯCLN(18, 12): một phép chia lấy dư thay cho nhiều phép trừ.
Trong code, vòng lặp chạy tới khi b = 0. Lúc đó a giữ số chia cuối cùng, chính là ƯCLN. Không cần a ≥ b: nếu a nhỏ hơn b thì bước đầu a % b = a, hai số tự đổi chỗ.
def ucln(a, b): while b != 0: a, b = b, a % b return a
print(ucln(48, 18)) # 6
# Python có sẵn hàm:from math import gcdprint(gcd(48, 18)) # 6#include <iostream>#include <numeric> // std::gcd (C++17)using namespace std;
long long ucln(long long a, long long b) { while (b != 0) { long long r = a % b; a = b; b = r; } return a;}
int main() { cout << ucln(48, 18) << endl; // 6 cout << gcd(48, 18) << endl; // 6, hàm có sẵn return 0;}Nhanh đến đâu? Sau một bước, cặp (a, b) thành (b, r), và số dư r luôn nhỏ hơn :
- Nếu b ≤ thì r < b ≤ .
- Nếu b > thì a chỉ chứa được một lần b, nên r = a - b < .
Sau bước thứ hai, r trở thành số lớn của cặp, tức là cứ hai bước thì số lớn giảm còn chưa tới một nửa. Từ 1018, giảm một nửa khoảng 60 lần là về 1 (vì 260 ≈ 1018), nên thuật toán cần chưa tới 120 bước. Thực tế trường hợp xấu nhất chỉ khoảng 90 bước (xem bài 6).
Bội chung nhỏ nhất
Phần tiêu đề “Bội chung nhỏ nhất”Các bội của 12: 12, 24, 36, 48, … Các bội của 18: 18, 36, 54, … BCNN(12, 18) = 36.
Với hai số a, b luôn có: ƯCLN × BCNN = a × b. Vì sao? Với 12 và 18, ƯCLN là 6: 12 = 6 × 2 và 18 = 6 × 3, hai phần riêng 2 và 3 không còn ước chung nào ngoài 1. Bội chung phải chứa đủ phần chung 6 và cả hai phần riêng, nên BCNN = 6 × 2 × 3 = 36. Nhân thêm ƯCLN: 6 × 36 = (6 × 2) × (6 × 3) = 12 × 18.
Gọi g = ƯCLN(a, b), suy ra:
Lưu ý: phải chia trước rồi mới nhân. Viết a * b / ucln(a, b) thì với a, b
khoảng 1010, tích a × b = 1020 đã vượt quá long long của C++ (khoảng
9,2 × 1018), cho kết quả sai dù BCNN thật vẫn nhỏ.
ƯCLN và BCNN của nhiều số
Phần tiêu đề “ƯCLN và BCNN của nhiều số”Làm lần lượt từng số: ƯCLN(a, b, c) = ƯCLN(ƯCLN(a, b), c). BCNN cũng vậy.
| Số | 12 | 18 | 24 | 30 |
|---|---|---|---|---|
| ƯCLN tính đến đây | 12 | 6 | 6 | 6 |
| BCNN tính đến đây | 12 | 36 | 72 | 360 |
Mẹo: bắt đầu ƯCLN từ 0 (0 chia hết cho mọi số, nên ƯCLN(0, x) = x) và BCNN từ 1 (BCNN(1, x) = x), rồi gộp từng số vào.
Nguyên tố cùng nhau và phân số tối giản
Phần tiêu đề “Nguyên tố cùng nhau và phân số tối giản”- Hai số có ƯCLN bằng 1 gọi là nguyên tố cùng nhau, ví dụ 8 và 15.
- Phân số tối giản khi a và b nguyên tố cùng nhau. Muốn rút gọn, chia cả tử và mẫu cho ƯCLN (ƯCLN(48, 18) = 6 như ví dụ ở trên):
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 23 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. Tính ƯCLN và BCNN
Phần tiêu đề “Nhóm 1. Tính ƯCLN và BCNN”Bài 1. Ước chung lớn nhất
Phần tiêu đề “Bài 1. Ước chung lớn nhất”Nhập hai số nguyên dương a, b (a, b ≤ 1018). In ra ƯCLN(a, b).
Ví dụ: nhập 12 18 thì in ra 6.
Kiểm tra: nhập 1071 462.
Bài 2. Bội chung nhỏ nhất
Phần tiêu đề “Bài 2. Bội chung nhỏ nhất”Nhập hai số nguyên dương a, b (a, b ≤ 109). In ra BCNN(a, b).
Ví dụ: nhập 12 18 thì in ra 36.
Kiểm tra: nhập 123456 7890.
Bài 3. ƯCLN của nhiều số
Phần tiêu đề “Bài 3. ƯCLN của nhiều số”Dòng đầu là n (n ≤ 105). Dòng thứ hai có n số nguyên dương, mỗi số không quá 1018. In ra ƯCLN của n số đó.
Ví dụ:
| Nhập | In ra |
|---|---|
312 18 24 | 6 |
Kiểm tra: nhập
512 18 24 30 36Bài 4. BCNN của các số từ 1 đến n
Phần tiêu đề “Bài 4. BCNN của các số từ 1 đến n”Nhập số nguyên dương n (n ≤ 40). In ra BCNN(1, 2, …, n), tức là số nhỏ nhất chia hết cho mọi số từ 1 đến n.
Ví dụ: nhập 10 thì in ra 2520.
Kiểm tra: nhập 20.
Bài 5. Nguyên tố cùng nhau
Phần tiêu đề “Bài 5. Nguyên tố cùng nhau”Nhập hai số nguyên dương a, b (a, b ≤ 1018). In ra YES nếu a và b nguyên tố cùng nhau (ƯCLN bằng 1), ngược lại in ra NO.
Ví dụ: nhập 8 15 thì in ra YES.
Kiểm tra: nhập 391 667.
Bài 6. Số bước của thuật toán Euclid
Phần tiêu đề “Bài 6. Số bước của thuật toán Euclid”Nhập hai số nguyên dương a, b (a, b ≤ 1018). Chạy thuật toán Euclid: mỗi bước thay (a, b) bằng (b, a % b), dừng khi b = 0. In ra số bước đã thực hiện.
Ví dụ: nhập 1071 462 thì in ra 3.
Kiểm tra: nhập 832040 514229.
Nhóm 2. Phân số
Phần tiêu đề “Nhóm 2. Phân số”Bài 7. Rút gọn phân số
Phần tiêu đề “Bài 7. Rút gọn phân số”Nhập hai số nguyên dương a, b (a, b ≤ 1018). In ra phân số ở dạng tối giản, theo dạng tử/mẫu.
Ví dụ: nhập 12 18 thì in ra 2/3.
Kiểm tra: nhập 1071 462.
Bài 8. Cộng hai phân số
Phần tiêu đề “Bài 8. Cộng hai phân số”Nhập bốn số nguyên dương a, b, c, d (mỗi số không quá 109). In ra ở dạng tối giản tử/mẫu.
Ví dụ: nhập 1 6 1 10 thì in ra 4/15.
Kiểm tra: nhập 7 12 5 18.
Bài 9. Hai phân số bằng nhau
Phần tiêu đề “Bài 9. Hai phân số bằng nhau”Nhập bốn số nguyên dương a, b, c, d (mỗi số không quá 1018). In ra YES nếu , ngược lại in ra NO.
Ví dụ: nhập 2 3 4 6 thì in ra YES.
Kiểm tra: nhập 1071 462 51 22.
Bài 10. Tổng các phân số có tử số 1
Phần tiêu đề “Bài 10. Tổng các phân số có tử số 1”Nhập số nguyên dương n (n ≤ 20). In ra ở dạng tối giản tử/mẫu.
Ví dụ: nhập 4 thì in ra 25/12.
Kiểm tra: nhập 10.
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. Cắt hình vuông lớn nhất
Phần tiêu đề “Bài 11. Cắt hình vuông lớn nhất”Có tấm bìa hình chữ nhật kích thước a × b (a, b ≤ 109). Cần cắt hết tấm bìa thành các hình vuông bằng nhau, cạnh là số nguyên, càng lớn càng tốt. In ra cạnh hình vuông và số hình vuông cắt được.
Ví dụ: nhập 12 18 thì in ra 6 6.
Kiểm tra: nhập 1071 462.
Bài 12. Hai đèn nhấp nháy
Phần tiêu đề “Bài 12. Hai đèn nhấp nháy”Đèn xanh cứ a giây sáng một lần, đèn đỏ cứ b giây sáng một lần (a, b ≤ 109). Lúc 0 giây cả hai cùng sáng. Hỏi sau bao nhiêu giây thì hai đèn lại cùng sáng lần tiếp theo?
Ví dụ: nhập 12 18 thì in ra 36.
Kiểm tra: nhập 1234 5678.
Bài 13. Chia nhóm nam nữ
Phần tiêu đề “Bài 13. Chia nhóm nam nữ”Lớp có a bạn nam và b bạn nữ (a, b ≤ 1018). Cô muốn chia lớp thành nhiều nhóm nhất sao cho các nhóm có số nam bằng nhau và số nữ bằng nhau. In ra số nhóm, số nam và số nữ mỗi nhóm.
Ví dụ: nhập 12 18 thì in ra 6 2 3.
Kiểm tra: nhập 1071 462.
Bài 14. Hai bánh răng
Phần tiêu đề “Bài 14. Hai bánh răng”Bánh răng A có a răng, bánh răng B có b răng ăn khớp với nhau (a, b ≤ 109). Đánh dấu một cặp răng đang chạm nhau. Hỏi bánh A và bánh B quay ít nhất bao nhiêu vòng thì cặp răng đó lại chạm nhau? In ra số vòng của A và số vòng của B.
Ví dụ: nhập 48 18 thì in ra 3 8.
Kiểm tra: nhập 1234 5678.
Bài 15. Điểm nguyên trên đoạn thẳng
Phần tiêu đề “Bài 15. Điểm nguyên trên đoạn thẳng”Nhập bốn số nguyên x1, y1, x2, y2 (giá trị tuyệt đối không quá 109, hai điểm khác nhau). Đếm số điểm có cả hai tọa độ nguyên nằm trên đoạn thẳng nối (x1, y1) với (x2, y2), kể cả hai đầu mút.
Ví dụ: nhập 0 0 4 6 thì in ra 3.
Kiểm tra: nhập 0 0 1071 462.
Bài 16. Chia hết cho a hoặc b
Phần tiêu đề “Bài 16. Chia hết cho a hoặc b”Nhập ba số nguyên dương n, a, b (n ≤ 1018, a, b ≤ 109). Đếm các số từ 1 đến n chia hết cho a hoặc chia hết cho b.
Ví dụ: nhập 20 4 6 thì in ra 7.
Kiểm tra: nhập 1000000000000000000 6 4.
Bài 17. Trồng cây quanh vườn
Phần tiêu đề “Bài 17. Trồng cây quanh vườn”Một mảnh vườn hình chữ nhật có hai cạnh a mét và b mét (a, b ≤ 1018). Người ta trồng cây quanh bờ vườn sao cho 4 góc đều có cây, các cây liền nhau cách đều nhau một số nguyên mét, và khoảng cách đó lớn nhất có thể. In ra khoảng cách giữa hai cây liền nhau và số cây cần trồng.
Ví dụ: nhập 12 18 thì in ra 6 10.
Kiểm tra: nhập 1071 462.
Nhóm 4. Vận dụng
Phần tiêu đề “Nhóm 4. Vận dụng”Bài 18. Số ước chung của nhiều số
Phần tiêu đề “Bài 18. Số ước chung của nhiều số”Dòng đầu là n (n ≤ 105). Dòng thứ hai có n số nguyên dương, mỗi số không quá 1012. In ra số lượng ước chung của n số đó.
Ví dụ:
| Nhập | In ra |
|---|---|
212 18 | 4 |
Kiểm tra: nhập
3360 840 1260Bài 19. ƯCLN với số rất lớn
Phần tiêu đề “Bài 19. ƯCLN với số rất lớn”Dòng đầu là số nguyên dương a có không quá 105 chữ số. Dòng thứ hai là số nguyên dương b (b ≤ 109). In ra ƯCLN(a, b).
Ví dụ:
| Nhập | In ra |
|---|---|
100000000000000000000024 | 8 |
Kiểm tra: nhập
123456789123456789123456789999999999Bài 20. Tìm hai số biết ƯCLN và BCNN
Phần tiêu đề “Bài 20. Tìm hai số biết ƯCLN và BCNN”Nhập hai số nguyên dương g, l (g ≤ l ≤ 1012). Tìm hai số nguyên dương a ≤ b có ƯCLN(a, b) = g, BCNN(a, b) = l và tổng a + b nhỏ nhất. In ra a và b; nếu không có thì in ra -1.
Ví dụ: nhập 2 12 thì in ra 4 6.
Kiểm tra: nhập 6 360.
Bài 21. Đếm số nguyên tố cùng nhau với n
Phần tiêu đề “Bài 21. Đếm số nguyên tố cùng nhau với n”Nhập số nguyên dương n (n ≤ 106). Đếm các số y từ 1 đến n mà y và n nguyên tố cùng nhau.
Ví dụ: nhập 12 thì in ra 4.
Kiểm tra: nhập 2026.
Bài 22. Đoạn liên tiếp dài nhất có ƯCLN lớn hơn 1
Phần tiêu đề “Bài 22. Đoạn liên tiếp dài nhất có ƯCLN lớn hơn 1”Dòng đầu là n (n ≤ 2000). Dòng thứ hai có n số nguyên dương, mỗi số không quá 109. Tìm độ dài lớn nhất của một đoạn các số liên tiếp trong dãy mà ƯCLN của cả đoạn lớn hơn 1. Nếu không có đoạn nào thì in ra 0.
Ví dụ:
| Nhập | In ra |
|---|---|
52 4 8 3 9 | 3 |
Kiểm tra: nhập
84 6 3 9 7 14 21 5Bài 23. Cặp có ƯCLN lớn nhất
Phần tiêu đề “Bài 23. Cặp có ƯCLN lớn nhất”Dòng đầu là n (2 ≤ n ≤ 105). Dòng thứ hai có n số nguyên dương a1, a2, …, an (ai ≤ 106). Chọn hai phần tử ở hai vị trí khác nhau sao cho ƯCLN của chúng lớn nhất. In ra ƯCLN đó.
Ví dụ:
| Nhập | In ra |
|---|---|
54 6 9 15 8 | 4 |
Kiểm tra: nhập
61000000 999999 500000 333333 7 14