Ước chung lớn nhất và bội chung nhỏ nhất số lớn

Mục tiêu kiến thức

• Cài đặt thuật toán Euclid tìm ước chung lớn nhất (GCD) bằng vòng lặp với độ phức tạp O(log(min(A, B))).
• Hiểu rõ hiện tượng tràn số nguyên (Integer Overflow) trong C++ và cách phòng tránh bằng kiểu dữ liệu long long.
• Kỹ thuật tính bội chung nhỏ nhất (LCM) an toàn: chia trước nhân sau lcm(A, B) = Agcd(A, B) × B.

Mô tả bài toán

Hệ thống mạng nơ-ron phân tán của AI Empire Academy cần đồng bộ hóa chu kỳ cập nhật trọng số giữa hai cụm GPU độc lập. Cụm thứ nhất phát tín hiệu sau mỗi A nano-giây, cụm thứ hai phát tín hiệu sau mỗi B nano-giây (1 ≤ A, B ≤ 10⁹).

Bạn hãy viết chương trình C++:

• Tìm ước chung lớn nhất (UCLN) của A và B.
• Tìm thời điểm đồng bộ hóa đầu tiên, chính là bội chung nhỏ nhất (BCNN) của A và B.

Cảnh báo kỹ thuật: Vì A và B có thể lên tới 10⁹, tích A × B có thể đạt tới 10¹⁸, vượt quá giới hạn cực đại của kiểu số nguyên 32-bit int (tối đa ≈ 2.14 × 10⁹). Bắt buộc phải sử dụng kiểu dữ liệu 64-bit có dấu long long. Hơn nữa, ngay cả khi dùng long long, nếu viết biểu thức (A * B) / gcd(A, B) thì phép nhân A * B vẫn có thể gây tràn số nếu giá trị vượt 9 × 10¹⁸. Kỹ thuật chuẩn là thực hiện phép chia trước: (A / gcd(A, B)) * B.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ A, B ≤ 10⁹.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.