A/B + C/D

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 $\frac{A}{B}$ and $\frac{C}{D}$; call the results $\frac{a}{b}$ and $\frac{c}{d}$, where $a$ and $b$ are coprime, and so as $c$ and $d$.

Now, let $b = kx$, $d = ky$, where $x$ and $y$ are coprime; this means $k$ is their GCD. Thus our sought value is $\frac{a}{kx} + \frac{c}{ky} = \frac{ay+cx}{kxy}$. Since each of $(a,x), (c,y), (x,y)$ are coprime, $ay+cx$ and $xy$ will be coprime. (Suppose they don’t, and suppose they share a common prime factor $p$ that divides $x$. Clearly $cx$ is divisible by $p$, so to make $ay+cx$ divisible by $p$, we need $ay$ divisible by $p$. But since $p$ is a factor of $x$, and $a$ and $y$ are both coprime to $x$, both $a$ and $y$ cannot have $p$ as a factor, contradiction.)

Thus, if $ay+cx$ is also coprime with $k$, we’re done; we have $E = ay+cx$ and $F = kxy$, and both fit inside our limit. The problem is when $ay+cx$ is not coprime with $k$, and consequently $ay+cx, kxy$ are not necessarily within our limit.

Here’s the magic. $a$ is within limit, and if we take $a' \equiv a \pmod k$ such that $a' \in [-\frac{k}{2}, \frac{k}{2})$, we have $|a'| \le \frac{k}{2}$. Also, $ky = d$ fits within $p$-bit integer, so $a'y \le \frac{ky}{2} = \frac{d}{2}$ must fit within $(p-1)$-bit integer! We do the same with $c$, getting $c'$. Additionally, the sum of two $(p-1)$-bit integers fits within $p$-bit integer! This allows us to obtain a number $a'y+c'x \equiv ay+cx \pmod k$ which fits within our limit.

Next, suppose that $\gcd(ay+cx, k) = g$. Then we also have $\gcd(a'y+c'x, k) = g$, because $ay+cx$ and $a'y+c'x$ differ by a multiple of $k$. This allows us to find the value of $g$. Thus, representing $k = gk'$, we have $F = k'xy$, which by assumption fits in our limit. We also know that $E = \frac{ay+cx}{g}$, and so it will be within limit, but how to divide by $g$?

We do the same thing as above. We can compute $a = a' + qk = a' + qk'g$, and thus $ay = a'y + qyk'g$. Thus we can add $qyk' = \frac{(a-a')}{g} \cdot y$ into the sum, while retaining $a'y$ for later. Similarly, if we let $c = c' + rk$, we can add $rxk' = \frac{(c-c')}{g} \cdot x$ into the sum, keeping $c'x$. Finally, since now $a'y + c'x$ fits in a single integer, we can also compute $\frac{a'y+c'x}{g}$ directly, adding into the sum too and thus producing the value of $E$.

And there we are.

1. Simplify $\frac{A}{B}$ and $\frac{C}{D}$ into $\frac{a}{b}$ and $\frac{c}{d}$ where $a,b$ are coprime, and $c,d$ are coprime. (This can be done by finding the respective GCD by Euclidean algorithm and dividing each from the GCD.)
2. Compute $k = \gcd(b,d)$, and compute $x = \frac{b}{k}, y = \frac{d}{k}$.
3. Compute $a', c'$ such that $a' \equiv a \pmod k, c' \equiv c \pmod k$, and $a', c' \in [-\frac{k}{2}, \frac{k}{2})$. (This can be done by simply using the modulo operator, and in case the result is $\frac{k}{2}$ or greater, subtract $k$ from it.
4. Compute $g = \gcd(a'y+c'x, k)$, and compute $k' = \frac{k}{g}$
5. Compute $F = k'xy$.
6. Compute $E = \frac{a-a'}{g} \cdot y + \frac{c-c'}{g} \cdot x + \frac{a'y+c'x}{g}$.