LCM_GCD - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: jeevanjyot
Testers: nishant403, satyam_343
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You are given integers A and B. Find the smallest possible value of \text{lcm}(A, X) - \gcd(B, X) across all positive integers X.

EXPLANATION:

The answer is probably guessable by looking at the sample tests and/or working out a few small examples.

Short answer

The answer is simply

A - \gcd(A, B)
Long answer

I’ll focus a bit on how one can derive this without guessing.

Our expression is \text{lcm}(A, X) - \gcd(B, X).
In particular, the first part of that expression is always a multiple of A.

Let’s fix the value of this lcm: suppose we choose X such that \text{lcm}(A, X) = k\cdot A.
Notice that this means that X is a factor of k\cdot A.

Our objective is now to maximize \gcd(B, X), since that’s what would make the difference as small as possible.
For \gcd(B, X) to be as large as possible, X should contain as many prime factors in common with B as possible.

Along with the constraint that X is a factor of k\cdot A, this tells us that the best choice of X is k\cdot A itself; choosing a strict factor isn’t going to help us increase the gcd.

Ok, so now we have k\cdot A - \gcd(B, k\cdot A).
What value of k minimizes this?

Intuitively, k = 1 seems good; after all, the second part is a factor of B so will always be \leq B no matter how large k is; while the first part keeps increasing without bound.
k = 1 gives us A - \gcd(A, B), which if you notice is the expression given in the “short answer” above.

Let’s try to prove that this is optimal.

Proof

First, notice that for any k\geq 1, we have \gcd(B, k\cdot A) \leq \gcd(k\cdot B, k\cdot A); since k\cdot B is a multiple of B.

But it’s also true that \gcd(k\cdot B, k\cdot A) = k\cdot\gcd(A, B).
So, we have \gcd(B, k\cdot A) \leq k\cdot \gcd(A, B).

This means that

k\cdot A - \gcd(B, k\cdot A) \geq k\cdot A - k\cdot\gcd(A, B) \\ k\cdot A - \gcd(B, k\cdot A) \geq k\cdot(A - \gcd(A, B)) \\ k\cdot A - \gcd(B, k\cdot A) \geq A - \gcd(A, B)

which is exactly what we set out to prove!

All that remains is computing the answer quickly, which requires us to compute \gcd(A, B) quickly.
This can be done in \mathcal{O}(\log\min(A, B)) using the Euclidean algorithm.

TIME COMPLEXITY:

\mathcal{O}(\log\min(A, B)) per testcase.

CODE:

Code (Python) 
from math import gcd
for _ in range(int(input())):
    a, b = map(int, input().split())
    print(a - gcd(a, b))
3 Likes