Ước chung lớn nhất (Euclid)

Nguồn: CLUE OJ Độ khó: Dễ Thuật toán Euclid Vòng lặp while

Đề bài

Cho hai số nguyên dương $a$ và $b$. Hãy tìm ước chung lớn nhất (UCLN) của $a$ và $b$ bằng thuật toán Euclid.

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 UCLN của $a$ và $b$.

Giới hạn:

• $1 \le 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 3

Ví dụ 1 – output

3

Ví dụ 2 – input

3 1

Ví dụ 2 – output

1

Ví dụ 3 – input

10 20

Ví dụ 3 – output

10

Nguồn: phỏng theo bài "ƯỚC CHUNG LỚN NHẤT" – vinhdinhcoder.net (chủ đề Lặp WHILE).

Lời mở đầu

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, và chỉ cần một vòng while. Bài này so sánh hai phiên bản: trừ liên tiếp (dễ hiểu nhưng có thể chạy $10^{18}$ bước) và chia lấy dư (chưa tới 90 bước). Ghi chú: đề gốc không có giới hạn dữ liệu, mình bổ sung $1 \le a, b \le 10^{18}$ (dùng long long).

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ưởngchia lấy dưLờ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ỏ: hai số bằng nhau, có số 1, một số là bội số kia, hai số Fibonacci liên tiếp
9–11, 17	Một số cỡ $10^{18}$, số kia rất nhỏ hoặc hai số liền nhau – trừ liên tiếp / duyệt ước phải chạy cỡ $10^{18}$ bước
12	Hai số Fibonacci liên tiếp lớn nhất $\le 10^{18}$: Euclid chạy nhiều vòng nhất (~85 vòng)
13–16, 18–20	Số vượt int: lũy thừa của 2, hai số bằng nhau, UCLN lớn, số ngẫu nhiên

Ý tưởngUCLN(a, b) = UCLN(b, a % b)

Euclid trừ: ước chung của $a$ và $b$ cũng là ước của $a - b$, nên $\text{UCLN}(a, b) = \text{UCLN}(a - b, b)$. Cứ lấy số lớn trừ số nhỏ tới khi hai số bằng nhau. Đúng, nhưng với $a = 10^{18}, b = 1$ phải trừ gần $10^{18}$ lần!

Euclid chia: trừ $b$ nhiều lần liên tiếp chính là lấy dư: $\text{UCLN}(a, b) = \text{UCLN}(b, a \bmod b)$, và khi $b = 0$ thì UCLN là $a$. Mỗi 2 vòng, số nhỏ giảm ít nhất một nửa → với số tới $10^{18}$ chỉ chưa tới 90 vòng.

Thứ tự gán

Trong vòng lặp phải lưu số dư ra biến tạm trước: r = a % b; a = b; b = r;. Nếu viết a = b; b = a % b; thì lúc tính a % b, $a$ đã bị ghi đè bằng $b$ → luôn ra 0.

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ảiEuclid chia lấy dư

Vòng while chạy chừng nào $b \ne 0$; khi thoát, đáp án nằm ở $a$.

C++▶ Chạy tay từng dòng codeLặp r = a % b; a = b; b = r cho tới khi b = 0.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Không cần đổi chỗ để $a \ge b$: nếu $a < b$ thì vòng đầu tiên a % b = a và hai số tự đổi chỗ cho nhau.
2. Biến r khai báo bên trong vòng lặp vì chỉ dùng tạm trong mỗi vòng.
3. Python có math.gcd, nhưng ở chương vòng lặp mình tự viết để hiểu thuật toá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.005s. 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ú
Euclid bằng phép trừ liên tiếp	16/20	sai test 9, 10, 11, 17
Duyệt $d$ từ $\min(a, b)$ giảm dần tới khi chia hết cả hai	15/20	sai test 10, 12, 14, 18, 20
Dùng int	10/20	sai test 9, 10, 12, 13, 14, 15, 16, 17, 18, 20
Gán sai thứ tự: a = b; b = a % b;	8/20	sai test 3, 5, 6, 7, 10, 11, 12, 14, 17, 18, 19, 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.005s	Full điểm
	Python	20/20	0.025s	Full điểm
Euclid trừ	C++	16/20	–	Mất 4 test
Duyệt ước	C++	15/20	–	Mất 5 test
Dùng int	C++	10/20	–	Mất 10 test
Gán sai thứ tự	C++	8/20	–	Mất 12 test

Ghi chú của mình: khi cập nhật nhiều biến cùng lúc trong vòng lặp (như a, b của Euclid), hãy dùng biến tạm để không đọc nhầm giá trị đã bị ghi đè.

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 😇