Sửa LCM tránh tràn

Bối cảnh

Một công thức LCM viết theo a * b / gcd(a,b) đúng về toán học, nhưng trong chương trình tích a*b có thể vượt miền trước khi phép chia diễn ra.

Bạn cần tổ chức phép tính theo thứ tự an toàn hơn.

Yêu cầu

1. Đọc hai số nguyên dương a, b.
2. Tính GCD bằng Euclid.
3. Tính LCM theo a / gcd(a,b) * b.
4. In LCM.

Yêu cầu tổ chức code

Tách gcdEuclid và lcmValue thành hai hàm.

Lưu ý: Online Judge chủ yếu kiểm tra tính đúng của output. Yêu cầu tổ chức code được dùng để rèn đúng kỹ năng của buổi học và sẽ được giảng viên quan sát khi chữa bài.

Input

Hai số nguyên dương a b.

Output

Một số nguyên là LCM.

Ràng buộc

1 ≤ a,b ≤ 10^9; LCM vừa trong long long.

Ví dụ 1

Input

1000000000 999999999

Output

999999999000000000

Giải thích

GCD của 1,000,000,000 và 999,999,999 là 1, nên LCM là tích của hai số. Giá trị vẫn nằm trong long long, nhưng nếu dùng int sẽ tràn.

Ví dụ 2

Input

12 18

Output

36

Giải thích

GCD(12,18)=6, vì vậy 12/6*18=36.

Thông tin học tập

• Module: M02
• Buổi: B08
• Loại bài: LAB
• Độ khó: Medium
• Concepts: debugging functions, gcd, lcm, overflow prevention
• Giới hạn kiến thức: B01-B08
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100