<![CDATA[A/B + C/D]]>

<![CDATA[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.

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.)
Compute $k = \gcd(b,d)$ , and compute $x = \frac{b}{k}, y = \frac{d}{k}$ .
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.
Compute $g = \gcd(a'y+c'x, k)$ , and compute $k' = \frac{k}{g}$
Compute $F = k'xy$ .
Compute $E = \frac{a-a'}{g} \cdot y + \frac{c-c'}{g} \cdot x + \frac{a'y+c'x}{g}$ .

]]>