Ước chung lớn nhất của hai số nguyên (VL14)

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp Mã bài VL14

Đề bài

Cho hai số nguyên $a$ và $b$ (có thể âm hoặc bằng $0$, nhưng không đồng thời bằng $0$). Hãy tìm ước chung lớn nhất (UCLN) của $a$ và $b$, tức là số nguyên dương lớn nhất mà cả $a$ và $b$ đều chia hết.

Dữ liệu vào:

Một dòng gồm hai số nguyên $a$ và $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:

• $|a|, |b| \le 10^4$
• $a, b$ không đồng thời bằng $0$

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

Ví dụ 1 – input

2 4

Ví dụ 1 – output

2

Ví dụ 2 – input

-2 -10

Ví dụ 2 – output

2

Ví dụ 3 – input

0 43

Ví dụ 3 – output

43

Giải thích:

• Ví dụ 1: $2$ là số dương lớn nhất chia hết cả $2$ và $4$.
• Ví dụ 2: UCLN không phụ thuộc dấu, $\text{UCLN}(-2, -10) = \text{UCLN}(2, 10) = 2$.
• Ví dụ 3: mọi số đều là ước của $0$ nên $\text{UCLN}(0, 43) = 43$.

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

Ý tưởng

UCLN chỉ phụ thuộc trị tuyệt đối, nên đổi a, b thành |a|, |b|. Sau đó dùng thuật toán Euclid: lặp (a, b) → (b, a % b) cho tới khi b = 0, lúc đó a là đáp án (vì UCLN(a, 0) = a).

Ví dụ -2 -10 → (2, 10) → (10, 2) → (2, 0) → 2.

Lưu ý / bẫy thường gặp

• Không lấy trị tuyệt đối: trong C++ phép % với số âm cho kết quả âm, nên ra -2 thay vì 2 (__gcd cũng vậy).
• Thử từ min(a, b) giảm dần sẽ sai khi có số 0 (UCLN(0, 43) = 43).
• Euclid bằng phép trừ a -= b lặp vô hạn khi có số 0.

Lời giải

Code chuẩn bên dưới đã chấm đúng toàn bộ 20 test trên CLUE OJ.

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 😇