For each pair of positive numbers a and b, print their greatest common divisor and least common multiple.
What to build
A program that finds the GCD and LCM of pairs of numbers.
Requirements
- Find the GCD with Euclid's algorithm.
- Compute the LCM by dividing by the GCD before multiplying.
- Use
long longwhere a result can be large.
Input
The first line has q (1 ≤ q ≤ 100). Each of the next q lines has a and b (1 ≤ a, b ≤ 1,000,000,000).
Output
One line per pair: the GCD and the LCM, separated by a space.
Constraints
1 ≤ q ≤ 100 and 1 ≤ a, b ≤ 1,000,000,000.
Example
Input:
2
12 18
7 5
Output:
6 36
1 35
Why it works
Any divisor of a and b also divides a % b, so replacing the pair by (b, a % b) keeps the same GCD while the numbers shrink quickly.
Examples
Example 1 · Input
2 12 18 7 5
Expected output
6 36 1 35
Example 2 · Input
1 100 100
Expected output
100 100
Hints
Hint 1
Euclid: while b is not 0, replace (a, b) with (b, a % b).
Hint 2
lcm = a / gcd * b: divide first, so the number stays small.
Hint 3
Use long long: the LCM can be close to 10^18.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
long long gcd(long long a, long long b) {
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
int main(void) {
int q;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
long long a, b;
scanf("%lld %lld", &a, &b);
long long g = gcd(a, b);
printf("%lld %lld\n", g, a / g * b);
}
return 0;
}