I was contacted by a friend that maintains an online judge, asking about the solution to a particular problem that has existed for how many days on an “easy” section.
Basically, the problem is this: given positive integers A, B, C, D, compute A/B + C/D and simplify it. You are guaranteed that if you represent A/B + C/D = E/F in lowest terms, then all of A,B,C,D,E,F fit in p-bit integers (in the problem, p = 64). Your task is to find this E and F.
How do you approach this problem? If you have an integer type that can support more than p bits (say, p = 32 and
long long on C++ that can fit 64 bits, or just use Java’s
BigInteger or Python’s built-in integer type), this is pretty easy. Otherwise, you might also try making BigInteger-like type; say, making a class containing two p-bit integers and implementing arithmetical operations with it.
I also found a solution that doesn’t involve those, but it’s terribly, terribly messy…
First, simplify and ; call the results and , where and are coprime, and so as and .
Now, let , , where and are coprime; this means is their GCD. Thus our sought value is . Since each of are coprime, and will be coprime. (Suppose they don’t, and suppose they share a common prime factor that divides . Clearly is divisible by , so to make divisible by , we need divisible by . But since is a factor of , and and are both coprime to , both and cannot have as a factor, contradiction.)
Thus, if is also coprime with , we’re done; we have and , and both fit inside our limit. The problem is when is not coprime with , and consequently are not necessarily within our limit.
Here’s the magic. is within limit, and if we take such that , we have . Also, fits within -bit integer, so must fit within -bit integer! We do the same with , getting . Additionally, the sum of two -bit integers fits within -bit integer! This allows us to obtain a number which fits within our limit.
Next, suppose that . Then we also have , because and differ by a multiple of . This allows us to find the value of . Thus, representing , we have , which by assumption fits in our limit. We also know that , and so it will be within limit, but how to divide by ?
We do the same thing as above. We can compute , and thus . Thus we can add into the sum, while retaining for later. Similarly, if we let , we can add into the sum, keeping . Finally, since now fits in a single integer, we can also compute directly, adding into the sum too and thus producing the value of .
And there we are.
- Simplify and into and where are coprime, and are coprime. (This can be done by finding the respective GCD by Euclidean algorithm and dividing each from the GCD.)
- Compute , and compute .
- Compute such that , and . (This can be done by simply using the modulo operator, and in case the result is or greater, subtract from it.
- Compute , and compute
- Compute .
- Compute .