Least Common Multiple
Bạn nhận được hai số nguyên dương a và b. Hãy trả về bội chung nhỏ nhất của chúng: số nguyên dương nhỏ nhất mà cả a và b đều chia hết.
Hàm
- ainteger
- số nguyên dương đầu tiên
- binteger
- số nguyên dương thứ hai
- Trả vềinteger
- số nguyên dương nhỏ nhất là bội số của cả a và b
Ràng buộc
1 ≤ a ≤ 1061 ≤ b ≤ 106- Đáp án nằm trong phạm vi số nguyên có dấu 32 bit:
lcm(a, b) ≤ 231-1. Tícha × bcó thể không nằm trong phạm vi đó.
Ví dụ
- Đầu vào
- a = 4b = 6
- Đầu ra
- 12
- Giải thích
- Các bội số của
6bắt đầu bằng 6, 12, 18; các bội số của4bắt đầu bằng 4, 8, 12. Số đầu tiên xuất hiện trong cả hai danh sách là12.
- Đầu vào
- a = 7b = 3
- Đầu ra
- 21
- Giải thích
7và3không có ước chung nào ngoài1, vì vậy bội chung nhỏ nhất của chúng bằng tích của chúng,21.
- Đầu vào
- a = 15b = 45
- Đầu ra
- 45
- Giải thích
15chia hết45, vì vậy45đã là bội số của cả hai và không có bội số nào của45nhỏ hơn.
Câu hỏi mở rộng
Bạn có thể tìm ước chung lớn nhất mà không dùng phép chia hay phép lấy số dư, chỉ dùng phép trừ và phép chia đôi không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Đáp án là một bội số của số lớn hơn. Bạn cần thử mọi số nằm giữa hay chỉ các bội số của số lớn hơn?
Ước chung lớn nhất (greatest common divisor) và bội chung nhỏ nhất (least common multiple) có mối liên hệ:
gcd(a, b) × lcm(a, b) = a × b. Thuật toán Euclid tìm ước chung lớn nhất chỉ trong vài chục bước.Tính ước chung lớn nhất, rồi trả về
a / gcd × b. Hãy chia trước: tícha × bcó thể vượt quá giới hạn của số nguyên 32 bit ngay cả khi đáp án vẫn nằm trong giới hạn.
Lời giải
Bội chung nhỏ nhất và ước chung lớn nhất liên hệ với nhau qua một đẳng thức: gcd(a, b) × lcm(a, b) = a × b. Vì vậy, cách tính nhanh là a × b / gcd(a, b). Tích có thể lên đến 10^12 và gây tràn số nguyên 32 bit ngay cả khi kết quả vẫn nằm trong giới hạn, vì vậy hãy chia cho gcd trước khi nhân.
Đếm tăng từ số lớn hơn
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Đáp án ít nhất bằng số lớn hơn. Bắt đầu với m bằng max(a, b) rồi tăng thêm 1 cho đến khi cả hai số đều chia hết cho nó; bạn thử các ứng viên theo thứ tự tăng dần, nên số đầu tiên thỏa mãn là số nhỏ nhất. Với 4 và 6, bạn thử từ 6 đến 11 rồi dừng ở 12. Vòng lặp (loop) luôn kết thúc vì a × b là một bội chung.
Số lượt thử xấp xỉ độ lớn của đáp án. Với hai số nguyên tố 46337 và 46327, đáp án là 2146654199, cần hơn hai tỷ lượt thử.
Thuật toán
- Đặt
mbằng giá trị lớn hơn giữaavàb. - Khi
m % ahoặcm % bkhác0, hãy cộng 1 vàom. - Trả về
m.
def lcm(a, b):
m = max(a, b)
while m % a != 0 or m % b != 0:
m += 1
return mTìm lần lượt các bội số của số lớn hơn
Ý tưởng
Đáp án phải là bội số của số lớn hơn, big, vì vậy hãy lần lượt thử big, 2 × big, 3 × big và dừng ở số đầu tiên chia hết cho số nhỏ hơn. Với 4 và 6, bạn thử 6, rồi đến 12.
Vì small × big luôn là bội chung, vòng lặp chạy nhiều nhất min(a, b) lần, ở đây tối đa là một triệu lần. Tốc độ đó đủ nhanh với các giới hạn này, nhưng số lần lặp vẫn tăng theo đầu vào. Với các số lên đến 10^18, cách này sẽ không đủ nhanh.
Thuật toán
- Gọi
biglà số lớn hơn vàsmalllà số nhỏ hơn. - Đặt
m = big. - Khi
m % smallkhác0, cộngbigvàom. - Trả về
m.
def lcm(a, b):
big, small = max(a, b), min(a, b)
m = big
while m % small != 0:
m += big
return mChia cho ước chung lớn nhất, rồi nhân
Ý tưởng
Phân tích cả hai số thành thừa số nguyên tố. Với mỗi số nguyên tố, ước chung lớn nhất lấy lũy thừa nhỏ hơn trong hai lũy thừa, còn bội chung nhỏ nhất lấy lũy thừa lớn hơn, nên chúng kết hợp lại chứa mỗi thừa số của a và b đúng một lần: gcd × lcm = a × b. Với 4 = 2² và 6 = 2 × 3, ước chung lớn nhất là 2 và bội chung nhỏ nhất là 2² × 3 = 12.
Thuật toán Euclid tìm ước chung lớn nhất trong O(log(min(a, b))) bước. Sau đó, tính a / gcd × b theo thứ tự đó: ước chung lớn nhất chia hết a, nên không có gì bị mất và không bước nào vượt quá đáp án. Phép tính a × b / gcd gây tràn số nguyên 32 bit khi a = b = 10^6, lúc đó tích là 10^12 còn đáp án chỉ là 10^6.
Thuật toán
- Sao chép
avàbvàoxvày. - Khi
ykhác0, thay(x, y)bằng(y, x % y). Lúc này,xlà ước chung lớn nhất. - Chia
achox. - Nhân kết quả với
brồi trả về.
def lcm(a, b):
x, y = a, b
while y != 0:
x, y = y, x % y
# x is gcd(a, b). Divide before multiplying.
return a // x * b
Lỗi thường gặp và trường hợp biên
- Tính
a × btrước. Trong Java, C, C++, C# và Rust, tích của hai số gần10^6sẽ tràn số nguyên 32 bit và cho kết quả sai hoặc âm (bản dựng gỡ lỗi của Rust sẽ gây lỗi panic), dù lcm vẫn nằm trong giới hạn. - Chia bằng số thực dấu phẩy động (floating point). Kết quả có thể là
2.146654199E9hoặc mất các chữ số cuối; hãy giữ mọi giá trị ở dạng số nguyên. - Chạy vòng lặp Euclid trực tiếp trên
avàb. Sau đó, chúng chứa gcd và0, vì vậy hãy thao tác trên các bản sao. - Cho rằng đáp án là
a × b. Điều đó chỉ đúng khi hai số không có thừa số chung:lcm(4, 6)là12, không phải24.
Câu hỏi thường gặp3
Công thức tính BCNN của hai số là gì?
lcm(a, b) = a × b / gcd(a, b), được tính bằng a / gcd(a, b) × b để không có giá trị trung gian nào vượt quá kết quả. Với 4 và 6, gcd là 2, và 4 / 2 × 6 = 12.
Độ phức tạp thời gian khi tính BCNN là bao nhiêu?
Với công thức gcd, độ phức tạp thời gian là O(log(min(a, b))), tương đương với độ phức tạp của thuật toán Euclid, và độ phức tạp không gian là O(1). Tăng dần theo bội số của số lớn hơn có độ phức tạp O(min(a, b)), còn đếm từng đơn vị có độ phức tạp O(lcm(a, b)).
Làm thế nào để tìm bội chung nhỏ nhất của nhiều hơn hai số?
Gộp danh sách: lcm(a, b, c) = lcm(lcm(a, b), c). Với [4, 6, 10], lcm(4, 6) = 12 và lcm(12, 10) = 60. Giá trị tích lũy tăng nhanh, vì vậy hãy dùng số nguyên 64 bit khi danh sách dài.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def lcm(a, b):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
a = 4 b = 6
Đầu ra mong đợi
12