Đề

Dùng hàm ucln(a, b) của mục 5.5.2 (thuật toán Euclid), viết thêm hàm bcnn(a, b) trả về

$$\text{BCNN}(a, b) = \frac{a \times b}{\text{ƯCLN}(a, b)}$$

tính bằng a * b // ucln(a, b). Chương trình chính đọc hai số nguyên dương ~a~, ~b~ và in ƯCLN rồi BCNN.

Dữ liệu vào

Một dòng chứa hai số nguyên dương ~a~ và ~b~, cách nhau một dấu cách.

Kết quả

Một dòng gồm hai số: ƯCLN và BCNN của ~a~ và ~b~, theo đúng thứ tự đó, cách nhau một dấu cách.

Ràng buộc

• ~1 \le a, b \le 10^{18}~.
• BCNN có thể tới khoảng ~10^{36}~; số nguyên Python không bị tràn, nhưng số thực (float) thì mất chính xác.

Ví dụ

Dữ liệu vào:

12 18

Kết quả:

6 36

Giải thích ví dụ

Bảng vết của ucln(12, 18) với phép gán đồng thời a, b = b, a % b:

ƯCLN = 6, BCNN = 12 × 18 // 6 = 216 // 6 = 36. Lưu ý hàm ucln làm thay đổi a, b của riêng nó (biến cục bộ, mục 5.4); chương trình chính vẫn giữ 12 và 18 để tính tiếp BCNN.

Ghi chú

• Dùng chia nguyên //: viết / thì in 36.0 (sai định dạng) và với số lớn còn sai giá trị.
• Không tách a, b = b, a % b thành hai lệnh a = b rồi b = a % b (mục 4.6.2).
• Thử lần lượt các số từ min(a, b) giảm dần để tìm ƯCLN vẫn ra đúng với số nhỏ, nhưng với hai số cỡ ~10^{18}~ nguyên tố cùng nhau thì cần tới ~10^{18}~ vòng lặp: bị Time Limit.
• Hệ thống chỉ so kết quả in ra; yêu cầu "dùng hàm ucln của mục 5.5.2, có ít nhất ba assert" là phần giảng viên kiểm khi chấm tay.

Nguồn trong sách: Bài C5-06, mục 5.10, giáo trình "Lập trình cơ sở với Python" — TS. Nguyễn Quốc Long · Mức: (**)