# GCDLM - Editorial

Author: notsoloud
Tester: apoorv_me
Editorialist: iceknight1093

1419

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))