Bội chung nhỏ nhất (Euclid)

Nguồn: CLUE OJ Độ khó: Dễ Thuật toán Euclid Tràn số

Đề bài

Cho hai số nguyên dương $a$ và $b$. Hãy tìm bội chung nhỏ nhất (BCNN) của $a$ và $b$, tức là số nguyên dương nhỏ nhất chia hết cho cả $a$ và $b$.

Dữ liệu vào:

Một dòng gồm hai số nguyên dương $a, b$ cách nhau bởi dấu cách.

Kết quả:

In ra BCNN của $a$ và $b$.

Giới hạn:

• $1 \le a, b \le 10^{18}$
• Dữ liệu đảm bảo $\text{BCNN}(a, b) \le 10^{18}$.

Subtask:

• Subtask 1 (40% số điểm): $a, b \le 10^6$.
• Subtask 2 (60% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

3 2

Ví dụ 1 – output

6

Ví dụ 2 – input

2 4

Ví dụ 2 – output

4

• Ví dụ 1: $6$ là số nhỏ nhất chia hết cho cả $3$ và $2$.
• Ví dụ 2: $4$ chia hết cho cả $2$ và $4$.

Nguồn: phỏng theo bài "BỘI CHUNG NHỎ NHẤT" – vinhdinhcoder.net (chủ đề Lặp WHILE).

Lời mở đầu

BCNN của hai số tới $10^{18}$: đi tìm từng bội chung thì quá chậm, còn công thức quen thuộc $a \cdot b / \text{UCLN}$ lại bị tràn số. Mình sẽ dùng thuật toán Euclid với vòng lặp while để tìm UCLN, rồi tính BCNN theo thứ tự "chia trước, nhân sau". Ghi chú: đề gốc viết "số nguyên dương" nhưng ràng buộc lại cho $0 \le a, b$; BCNN với số 0 không có nghĩa nên mình chốt $1 \le a, b \le 10^{18}$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngEuclid + chia trướcLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Test 1–8 thuộc subtask 1 ($a, b \le 10^6$), test 9–20 có số tới $10^{18}$.

Test	Nội dung kiểm tra
1–8	Số nhỏ: một số là bội của số kia, hai số bằng nhau, hai số nguyên tố gần $10^6$
9–10, 15–16	Một số rất lớn, số kia là 1, 2, 3 – Euclid trừ liên tiếp chạy $10^{18}$ bước; BCNN lẻ lớn hơn $2^{53}$ – double làm tròn sai
11, 17	Hai số nguyên tố cùng nhau cỡ $10^9$: BCNN gần $10^{18}$ – duyệt bội phải chạy $10^9$ vòng
12–14, 18–19	UCLN lớn: $a \cdot b$ vượt xa $9{,}2 \cdot 10^{18}$ – nhân trước chia sau bị tràn
20	Số ngẫu nhiên

Ý tưởngUCLN bằng Euclid, rồi BCNN = a / UCLN · b

Ta có công thức $\text{BCNN}(a, b) = \dfrac{a \cdot b}{\text{UCLN}(a, b)}$. Việc còn lại là tìm UCLN thật nhanh.

Thuật toán Euclid: $\text{UCLN}(x, y) = \text{UCLN}(y, x \bmod y)$, và $\text{UCLN}(x, 0) = x$. Vậy ta lặp: r = x % y; x = y; y = r; cho tới khi $y = 0$, lúc đó $x$ là UCLN. Mỗi 2 vòng, số nhỏ hơn giảm ít nhất một nửa nên với số tới $10^{18}$ chỉ cần chưa tới 90 vòng.

Chia trước, nhân sau

$a \cdot b$ có thể tới $10^{36}$ – tràn long long (tối đa khoảng $9{,}2 \cdot 10^{18}$) dù kết quả cuối chỉ $\le 10^{18}$. Vì UCLN chia hết $a$ nên ta tính a / g * b: phép chia ra số nguyên chính xác, và kết quả nhân xong chính là BCNN $\le 10^{18}$, không tràn.

Em nhập dữ liệu rồi bấm Tiếp để xem từng vòng lặp chạy thế nào:

a = b =

Ví dụ nhanh:

Lời giảiVòng lặp while của Euclid

Mình chép $a, b$ sang hai biến $x, y$ để chạy Euclid, giữ nguyên $a, b$ cho bước tính BCNN.

C++▶ Chạy tay từng dòng codeEuclid tìm UCLN, sau đó BCNN = a / g * b.

Dữ liệu vào (stdin) – sửa thoải mái3 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Không dùng __gcd hay gcd có sẵn: tự viết vòng lặp Euclid giúp em hiểu thuật toán, và chỉ mất 5 dòng.
2. a / g * b được tính từ trái sang phải: chia trước, nhân sau. Viết a * b / g là nhân trước – tràn số.
3. Python không bị tràn số nguyên, nhưng mình vẫn viết a // g * b cho giống C++ (và nhanh hơn khi số rất lớn).

Không gian$O(1)$

Thời gian$O(\log \min(a, b))$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Bản Python đúng 20/20 test, chạy lâu nhất 0.025s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Đúng Euclid nhưng tính a * b / g (nhân trước)	15/20	sai test 12, 13, 14, 18, 19
Duyệt các bội của số lớn tới khi chia hết cho số nhỏ	18/20	sai test 11, 17
Euclid bằng phép trừ liên tiếp	16/20	sai test 9, 10, 15, 16
Tính BCNN bằng double, in %.0f	16/20	sai test 11, 15, 16, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.004s	Full điểm
	Python	20/20	0.025s	Full điểm
Nhân trước chia sau	C++	15/20	–	Mất 5 test
Duyệt bội	C++	18/20	–	Mất 2 test
Euclid trừ	C++	16/20	–	Mất 4 test
Dùng double	C++	16/20	–	Mất 4 test

Ghi chú của mình: "chia trước, nhân sau" là mẹo chống tràn số dùng được ở rất nhiều bài – chỉ cần chắc chắn phép chia là chia hết.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇