407157: GYM102697 128 What the Frac (Harder Version)

Your 5-year-old cousin from the CodeRams Contest #5 (Problem 4) is now in 4th grade, and he is learning how to add fractions. Unfortunately, he doesn't really understand them, and he needs your help in adding two or more fractions together.

For this problem, you must write a program to add several positive fractions together.

Since the test cases can be large, you will need to use an efficient method to solve it.

When adding two fractions together, you first change the denominators into their LCM (least common multiple).

The LCM of two numbers $$$a$$$ and $$$b$$$ can be calculated using the following formula:

LCM($$$a$$$, $$$b$$$) = $$$\frac{a * b}{GCD(a, b)}$$$, where GCD represents the greatest common divisor of $$$a$$$ and $$$b$$$.

You can find the greatest common divisor (GCD) or $$$a$$$ and $$$b$$$ efficiently using the following recursive algorithm:

1. If $$$a$$$ is less than $$$b$$$, swap $$$a$$$ and $$$b$$$

2. If $$$b$$$ is equal to $$$0$$$, return $$$a$$$

3. Otherwise, return GCD($$$b$$$, $$$a$$$ mod $$$b$$$)

The only line of input consists of a mathematical operation involving at least two fractions, each in the form $$$a$$$/$$$b$$$, and addition operations only

If the answer simplifies to a whole number, print the number. Otherwise, output a single fraction $$$c$$$/$$$d$$$: the result of the addition of fractions described in the input, in simplest form. The answer will not be less than or equal to 0.

3/4 + 2/3 + 7/9

79/36

8/7 + 8/9 + 17/11 + 33/53 + 89/77 + 65/59

13993216/2167011

2/3 + 7/3

3

If your code passes the second example case in under a second, it is efficient enough. Also, all input and output numbers are guaranteed to fit inside of an "int" data type in Java, if you code your solution efficiently.