Page Contents
Least Common Multiple
Prepbuddy is very fond of solving maths problems. One day his teacher after taking a class on Least common multiple (LCM), gave him a question in which he was given two irreducible fractions and was asked to find their least common multiple — the smallest positive irreducible fraction P/QP/Q such that the result of the division of P/QP/Q to any of the given fractions is an integer.
Actually, Prepbuddy thought that he knows the concept very well but now he is having difficulty in coming up with the solution. Help him to come up with a solution
He knew that LCM is the smallest number that is divisible by all the given numbers whose LCM we are trying to find. The concept of least common multiple can be generalized to other objects in math, for example to fractions.
Input Format
The first line of input contains an integer TT denoting the number of test cases. The first line of each test case is described as a single line that contains four positive integers AA, BB, CC, DD, that correspond to irreducible fractions A/BA/B and C/DC/D. It is guaranteed that A/BA/B and C/DC/D are both irreducible.
Output Format
For each test case print two integers numerator and denominator of the fraction that is a least common multiple of the given A/BA/B and C/DC/D fractions.
Constraints
1≤T≤5∗1041≤T≤5∗104 1≤A,B,C,D≤1091≤A,B,C,D≤109
Time Limit
2 second
Example
Sample Input
2 9 5 12 5 1 10 3 100
Sample Output
36 5 3 10
Note : Please click on 1 or 2 ads to help us run this site and encourages us to provide you the solutions.
JULY 2021 CODING MARATHON
- Shortest String Solution
- Least Common Multiple Solution
- String Transformation Solution
- Dark Moments Solution
- Go Go Home Solution
- Construct Rectangle Solution
- Arrange Guest Solution
- New Array Subarray Solution