# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* notsoloud

*apoorv_me*

**Tester:***iceknight1093*

**Editorialist:**# 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))
```