Bội chung nhỏ nhất của hai số nguyên (VL16)

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

Đề bài

Bội chung nhỏ nhất (BCNN, tiếng Anh: least common multiple – LCM) của hai số nguyên $a$ và $b$ là số nguyên dương nhỏ nhất chia hết cho cả $a$ và $b$.

Cho hai số nguyên khác $0$ là $a$ và $b$ (có thể âm), hãy tìm BCNN của chúng.

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

Giới hạn:

• $-1000 \le a, b \le 1000$
• $a \ne 0$, $b \ne 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

1 3

Ví dụ 1 – output

3

Ví dụ 2 – input

-1 3

Ví dụ 2 – output

3

Giải thích:

• Ví dụ 1: $3$ là số dương nhỏ nhất chia hết cho cả $1$ và $3$.
• Ví dụ 2: $3$ chia hết cho $-1$ và $3$; BCNN luôn là số dương.

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

BCNN cũng chỉ phụ thuộc trị tuyệt đối. Với a, b > 0:

$$\text{BCNN}(a, b) = \frac{a \cdot b}{\text{UCLN}(a, b)}$$

Thầy tính UCLN bằng Euclid, rồi lấy a / g * b (chia trước để số nhỏ hơn).

Ví dụ -4 6 → |a| = 4, |b| = 6, g = 2 → 4 / 2 · 6 = 12.

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

• Không lấy trị tuyệt đối → kết quả âm hoặc sai.
• BCNN không phải a·b (chỉ đúng khi hai số nguyên tố cùng nhau), cũng không phải max(a, b).

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 😇