Loading...
Loading...
Loading...
Two local trains leave Dadar station at 6 AM together. One leaves every a minutes and the other every b minutes.
The station master wants two numbers. First, the largest slot length g (in minutes) such that both a and b are whole multiples of g. Second, the number of minutes after 6 AM when both trains next leave together.
Print both numbers.
Example 1
Input
12 18
Output
6 36
6 divides both 12 and 18. Both trains next leave together after 36 minutes.
Example 2
Input
7 7
Output
7 7
Equal intervals: both answers are 7.
Try the problem first. Open one hint at a time.
The second number is a multiple of both a and b, and the smallest such one.
For the first number, use the rule gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.
Then lcm(a, b) = a / gcd × b. Divide first, and keep the product in a long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor