Bỏ qua để đến nội dung

Ướ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 - 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á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\sqrt{a}, tức 109 bước với a = 1018, quá chậm. Thuật toán Euclid nhanh hơn rất nhiều.

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):

  1. Chia a cho b, được a = b × q + r (q là thương, r là số dư).
  2. Nếu r = 0 thì ƯCLN(a, b) = b, dừng.
  3. 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 gcd
print(gcd(48, 18)) # 6

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 a2\dfrac{a}{2}:

  • Nếu b ≤ a2\dfrac{a}{2} thì r < b ≤ a2\dfrac{a}{2}.
  • Nếu b > a2\dfrac{a}{2} thì a chỉ chứa được một lần b, nên r = a - b < a2\dfrac{a}{2}.

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

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:

BCNN(a,b)=ag×b\text{BCNN}(a, b) = \dfrac{a}{g} \times 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 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ỏ.

Làm lần lượt từng số: ƯCLN(a, b, c) = ƯCLN(ƯCLN(a, b), c). BCNN cũng vậy.

Số12182430
ƯCLN tính đến đây12666
BCNN tính đến đây123672360

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ố ab\dfrac{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 (ƯCLN(48, 18) = 6 như ví dụ ở trên): 4818=48:618:6=83\dfrac{48}{18} = \dfrac{48 : 6}{18 : 6} = \dfrac{8}{3}

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

Xem đáp số

21

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

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.

Xem đáp số

162344640

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

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ậpIn 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ả.

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

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.

Xem đáp số

NO

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

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.

Xem đáp số

28

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

Nhập hai số nguyên dương a, b (a, b ≤ 1018). In ra phân số ab\dfrac{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ả.

Nhập bốn số nguyên dương a, b, c, d (mỗi số không quá 109). In ra ab+cd\dfrac{a}{b} + \dfrac{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ả.

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 ab=cd\dfrac{a}{b} = \dfrac{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ả.

Nhập số nguyên dương n (n ≤ 20). In ra 11+12+⋯+1n\dfrac{1}{1} + \dfrac{1}{2} + \dots + \dfrac{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ả.

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.

Xem đáp số

21 1122

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

Đè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.

Xem đáp số

3503326

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

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.

Xem đáp số

21 51 22

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

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.

Xem đáp số

2839 617

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

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.

Xem đáp số

22

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

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.

Xem đáp số

333333333333333333

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

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.

Xem đáp số

21 146

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

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ậpIn 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ả.

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ậpIn 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ả.

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.

Xem đáp số

30 72

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

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.

Xem đáp số

1012

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

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ậpIn 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ả.

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ậpIn ra
5
4 6 9 15 8
4

Kiểm tra: nhập

6
1000000 999999 500000 333333 7 14
Xem đáp số

500000

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

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy