BL
U

12. Compute GCD and LCM

Easy

Problem Description

Given two non-negative integers AA and BB (not both zero), calculate their Greatest Common Divisor (gcd⁡(A,B)\gcd(A, B)) and Least Common Multiple (lcm(A,B)\text{lcm}(A, B)).

Recall:

lcm(A,B)=A×Bgcd⁡(A,B)\text{lcm}(A, B) = \frac{A \times B}{\gcd(A, B)}

If either A=0A = 0 or B=0B = 0, lcm(A,B)=0\text{lcm}(A, B) = 0.

Input Format

A single line containing two space-separated integers AA and BB.

Output Format

Print two space-separated integers: gcd⁡(A,B)\gcd(A, B) followed by lcm(A,B)\text{lcm}(A, B).

Example 1:
Input:
12 18
Output:
6 36
Explanation: gcd(12, 18) = 6. lcm(12, 18) = (12 * 18) / 6 = 36.
Example 2:
Input:
7 13
Output:
1 91
Explanation: 7 and 13 are coprime, so gcd is 1 and lcm is 7 * 13 = 91.
Example 3:
Input:
15 0
Output:
15 0
Explanation: gcd(15, 0) = 15; lcm with 0 is 0.
Constraints:
  • 0 <= A, B <= 10^9 (not both zero)
  • Time complexity target: O(log(min(A, B)))
  • Auxiliary space target: O(1)
Follow up:How does the Extended Euclidean algorithm compute modular inverses in cryptography?
1,180 Online