Bội số chung nhỏ nhất

Đề bài

Trả về bội số chung nhỏ nhất của a và b, là số dương nhỏ nhất mà cả hai đều chia hết. lcm(a, b) = a / gcd(a, b) × b.

Cài đặt hàm lcm(a, b).

a: Số dương thứ nhất. b: Số dương thứ hai.

Trả về lcm(a, b).

1 ≤ a, b ≤ 1.000.000.000

Ví dụ 1

Đầu vào:
a = 4
b = 6

Kết quả mong đợi:
expected = 12

Đầu vào:
long long a = 4;
long long b = 6;

Kết quả mong đợi:
long long expected = 12;

Đầu vào:
long a = 4;
long b = 6;

Kết quả mong đợi:
long expected = 12;

Các bội số của 4: 4, 8, 12…; các bội số của 6: 6, 12…; bội số chung đầu tiên là 12.

Ví dụ 2

Đầu vào:
a = 7
b = 7

Kết quả mong đợi:
expected = 7

Đầu vào:
long long a = 7;
long long b = 7;

Kết quả mong đợi:
long long expected = 7;

Đầu vào:
long a = 7;
long b = 7;

Kết quả mong đợi:
long expected = 7;

Bội số chung nhỏ nhất của một số với chính nó là chính số đó: 7.

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Dùng mối quan hệ giữa gcd và lcm thay vì đi tìm bội.

Gợi ý 2

Tính gcd trước, rồi kết hợp hai số cẩn thận.

Gợi ý 3

Chia trước khi nhân để giảm nguy cơ tràn số, kể cả với đầu vào lớn.

Độ phức tạp mong đợi

thời gian O(log min(a, b)), bộ nhớ phụ O(1)

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.