Left and Down

The sneaky part is that we minimize cost, not the number of operations.

A pair only costs money the first time we use it. After that, reusing it is free. So we are really asking:

How many different move vectors do we need?

And because $k \ge 1$, the answer is never more than $2$:

• use $(1,0)$ exactly $a$ times to remove the $x$ coordinate,
• use $(0,1)$ exactly $b$ times to remove the $y$ coordinate.

Both pairs are valid because their coordinates are between $0$ and $k$. So the answer is either $1$ or $2$. Nice. Tiny problem, big ego.

When is cost 1 possible?

Cost $1$ means we choose one pair $(dx,dy)$, pay for it once, and then reuse that same pair some number of times.

Suppose we use it $m$ times. Then the total movement is:

$$(m \cdot dx,\ m \cdot dy)$$

We need this to equal $(a,b)$, so:

$$m \cdot dx = a$$ $$m \cdot dy = b$$

Therefore, $m$ must divide both $a$ and $b$.

The largest possible such $m$ is:

$$g = \gcd(a,b)$$

Using $m=g$ gives the smallest possible integer step:

$$\left(\frac a g, \frac b g\right)$$

If even this smallest proportional step does not fit inside the allowed range $[0,k]$, then no one-pair strategy can work.

So cost $1$ is possible exactly when:

$$\frac a g \le k$$

and

$$\frac b g \le k$$

where $g = \gcd(a,b)$.

If both are true, print 1. Otherwise, print 2.

Why checking only $g$ is enough

Maybe it feels like we should try every common divisor. Nope.

If we use some common divisor $m$, the move is:

$$\left(\frac a m, \frac b m\right)$$

Larger $m$ means smaller coordinates in the move. Since $g$ is the largest common divisor, it gives the smallest possible move among all one-pair options.

So:

• if $\left(\frac a g, \frac b g\right)$ fits, answer is $1$;
• if it does not fit, every other valid divisor gives an even bigger move, so answer cannot be $1$.

Then answer is $2$, because we already know $2$ always works.

Complexity: $O(\log \min(a,b))$ per test case because of gcd.