Ước chung lớn nhất, bội chung nhỏ nhất - thuật toán Euclid

Mức độ: Cơ bản

Ước chung lớn nhất (ƯCLN, tiếng Anh là gcd) và bội chung nhỏ nhất (BCNN, tiếng Anh là lcm) 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 10¹⁸ chỉ trong vài chục bước.

Ướ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 √a, tức 10⁹ bước với a = 10¹⁸, quá chậm. Thuật toán Euclid nhanh hơn rất nhiều.

Ý tưởng của thuật toán Euclid

Nhận xét: nếu a và b cùng chia hết cho một số d thì a - b cũng chia hết cho d. Ví dụ 18 và 12 cùng chia hết cho 6, nên 18 - 12 = 6 cũng chia hết cho 6. Ngược lại, nếu b và a - b cùng chia hết cho d thì a cũng chia hết cho d. Nghĩa là a, b và b, a - b có cùng các ước chung. Vậy ƯCLN(a, b) = ƯCLN(b, a - b): thay số lớn bằng hiệu, ƯCLN không đổi.

Trừ b nhiều lần cho tới khi không trừ được nữa chính là lấy số dư a % b. Vậy:

• ƯCLN(a, b) = ƯCLN(b, a % b)
• ƯCLN(a, 0) = a (mọi số đều là ước của 0)

Lặp lại cho tới khi số thứ hai bằng 0. Chạy tay với a = 1071, b = 462:

a	b	a % b
1071	462	147
462	147	21
147	21	0
21	0	dừng

ƯCLN(1071, 462) = 21, chỉ sau 3 phép chia.

Hình ảnh dễ nhớ: có tấm bìa hình chữ nhật 1071 × 462. Cắt đi các hình vuông cạnh 462 nhiều nhất có thể, còn lại hình chữ nhật 462 × 147. Lại cắt hình vuông cạnh 147, còn 147 × 21. Cắt tiếp thì vừa hết. Hình vuông cuối cùng có cạnh 21, và tấm bìa ban đầu lát kín được bằng các hình vuông cạnh 21.

Python

def ucln(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(ucln(1071, 462))     # 21

# Python có sẵn hàm:
from math import gcd
print(gcd(1071, 462))      # 21

C++

#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(1071, 462) << endl;   // 21
    cout << gcd(1071, 462) << endl;    // 21, hàm có sẵn
    return 0;
}

Nhanh đến đâu? Cứ sau hai bước, số lớn giảm còn chưa tới một nửa. Với số đến 10¹⁸, thuật toán chỉ cần khoảng 90 bước trong trường hợp xấu nhất.

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. Kiểm tra: 6 × 36 = 216 = 12 × 18. Vậy:

BCNN(a, b) = a / ƯCLN(a, b) × b

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 10¹⁰, tích a × b = 10²⁰ đã vượt quá long long của C++ (khoảng 9,2 × 10¹⁸), cho kết quả sai dù BCNN thật vẫn nhỏ.

Ư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 (vì ƯCLN(0, x) = x) và BCNN từ 1, rồi gộp từng số vào.

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ố a / b 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: 1071 / 462 = (1071 : 21) / (462 : 21) = 51 / 22.

Luyện tập

Gồm 21 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

Bài 1. Ước chung lớn nhất

Nhập hai số nguyên dương a, b (a, b ≤ 10¹⁸). In ra ƯCLN(a, b).

Ví dụ: nhập 12 18 thì in ra 6.

Kiểm tra: nhập 1071 462.

Xem đáp số

21

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Bội chung nhỏ nhất

Nhập hai số nguyên dương a, b (a, b ≤ 10⁹). In ra BCNN(a, b).

Ví dụ: nhập 12 18 thì in ra 36.

Kiểm tra: nhập 123456 7890.

Xem đáp số

162344640

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. ƯCLN của nhiều số

Dòng đầu là n (n ≤ 10⁵). Dòng thứ hai có n số nguyên dương, mỗi số không quá 10¹⁸. In ra ƯCLN của n số đó.

Ví dụ:

Nhập	In ra
3 12 18 24	6

Kiểm tra: nhập

5
12 18 24 30 36

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

232792560

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Nguyên tố cùng nhau

Nhập hai số nguyên dương a, b (a, b ≤ 10¹⁸). 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.

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

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 ≤ 10¹⁸). 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.

Xem đáp số

28

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Phân số

Bài 7. Rút gọn phân số

Nhập hai số nguyên dương a, b (a, b ≤ 10¹⁸). In ra phân số a / b ở 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.

Xem đáp số

51/22

Hướng dẫn giải chi tiết: liên hệ tác giả.

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á 10⁹). In ra a / b + c / d ở 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.

Xem đáp số

31/36

Hướng dẫn giải chi tiết: liên hệ tác giả.

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á 10¹⁸). In ra YES nếu a / b = c / d, 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.

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Tổng các phân số 1/1 đến 1/n

Nhập số nguyên dương n (n ≤ 20). In ra 1/1 + 1/2 + … + 1/n ở 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.

Xem đáp số

7381/2520

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Bài toán thực tế

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 ≤ 10⁹). 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.

Xem đáp số

21 1122

Hướng dẫn giải chi tiết: liên hệ tác giả.

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 ≤ 10⁹). 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.

Xem đáp số

3503326

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Chia nhóm nam nữ

Lớp có a bạn nam và b bạn nữ (a, b ≤ 10¹⁸). 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.

Xem đáp số

21 51 22

Hướng dẫn giải chi tiết: liên hệ tác giả.

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 ≤ 10⁹). Đá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.

Xem đáp số

2839 617

Hướng dẫn giải chi tiết: liên hệ tác giả.

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á 10⁹, 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.

Xem đáp số

22

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Chia hết cho a hoặc b

Nhập ba số nguyên dương n, a, b (n ≤ 10¹⁸, a, b ≤ 10⁹). Đế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.

Xem đáp số

333333333333333333

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 17. Số ước chung của nhiều số

Dòng đầu là n (n ≤ 10⁵). Dòng thứ hai có n số nguyên dương, mỗi số không quá 10¹². In ra số lượng ước chung của n số đó.

Ví dụ:

Nhập	In ra
2 12 18	4

Kiểm tra: nhập

3
360 840 1260

Xem đáp số

12

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. ƯCLN với số rất lớn

Dòng đầu là số nguyên dương a có không quá 10⁵ chữ số. Dòng thứ hai là số nguyên dương b (b ≤ 10⁹). In ra ƯCLN(a, b).

Ví dụ:

Nhập	In ra
1000000000000000000000 24	8

Kiểm tra: nhập

123456789123456789123456789
999999999

Xem đáp số

27

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Tìm hai số biết ƯCLN và BCNN

Nhập hai số nguyên dương g, l (g ≤ l ≤ 10¹²). 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.

Xem đáp số

30 72

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Đếm số nguyên tố cùng nhau với n

Nhập số nguyên dương n (n ≤ 10⁶). Đế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.

Xem đáp số

1012

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 21. Đ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á 10⁹. 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
5 2 4 8 3 9	3

Kiểm tra: nhập

8
4 6 3 9 7 14 21 5

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.