GCDLM - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: notsoloud
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

1419

PREREQUISITES:

Basic math

PROBLEM:

There are two integers X and Y. In one move:

  • Alice will replace one of them with \gcd(X, Y); then
  • Bob will replace one of them with \text{lcm}(X, Y).

Find the minimum possible sum of the two integers after K moves.

EXPLANATION:

Walk through the moves and let’s see what happens.
Let G = \gcd(X, Y), and suppose Alice chooses to replace X in her move.
Bob is now left with G and Y. However, G is a factor of Y, meaning \text{lcm}(G, Y) = Y.
So,

  • If Bob chooses to replace Y with the lcm, nothing changes.
  • If Bob chooses to replace G with the lcm, both numbers become Y (and so will never change again).

The second case is trivial, so let’s analyze the first one more: it’s back to Alice with the numbers being Y and G.
Of course, \gcd(G, Y) = G. So, Alice’s moves are:

  • Replace G by G, which changes nothing and passes to Bob; or
  • Replace Y by G, at which point both numbers become G and never change again.

The last case is clearly the best for us, we end up with (G, G) and definitely can’t get lower than that.
So, if K \geq 2 the answer is just 2\cdot \gcd(X, Y).

That leaves K = 1, for which we go back to the start.
After Alice and Bob both make their moves, our possible end states are as follows:

  • (G, Y) and (Y, Y) if Alice replaced X.
  • (G, X) and (X, X) if Alice replaced Y.

In particular, we can always attain G and the smaller of X and Y, which is the best we can do.
So, for K = 1, the answer is \gcd(X, Y) + \min(X, Y).

\gcd(X, Y) can be computed quickly using the Euclidean algorithm; though the constraints here are small enough that \mathcal{O}(\sqrt{X}) factorization should be fast enough too.

TIME COMPLEXITY

\mathcal{O}(\log\min(X, Y)) per testcase.

CODE:

Editorialist's code (Python) 
from math import gcd
for _ in range(int(input())):
    x, y, k = map(int, input().split())
    if k >= 2: print(2*gcd(x, y))
    else: print(gcd(x, y) + min(x, y))