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}.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s