Maple and Multiplication

There are only three possible answers: $0$, $1$, or $2$. That is the whole problem. Tiny, but still easy to overthink if you start doing prime factorization gymnastics for no reason.

What One Operation Can Do

In one operation, we choose any positive integer $x$ and multiply either $a$ or $b$ by $x$.

So from $a$, we can reach any number of the form:

$$a \cdot x$$

where $x$ is a positive integer. That means $a$ can become exactly $b$ in one operation iff:

$$b = a \cdot x$$

for some integer $x$, which is exactly the same as saying:

$$a \mid b$$

Similarly, $b$ can become $a$ in one operation iff:

$$b \mid a$$

So:

• If $a = b$, answer is $0$.
• Else if $a$ divides $b$, multiply $a$ by $b/a$, answer is $1$.
• Else if $b$ divides $a$, multiply $b$ by $a/b$, answer is $1$.

Why Two Operations Are Always Enough

If neither number divides the other, we still need to make them equal somehow.

We are allowed to multiply both numbers, so just make them both equal to a common multiple. The dumbest possible common multiple is $a \cdot b$.

Starting from $a$:

$$a \cdot b = ab$$

Starting from $b$:

$$b \cdot a = ab$$

So in two operations:

1. Multiply $a$ by $b$.
2. Multiply $b$ by $a$.

Now both are $ab$.

Could the answer be more than $2$? Nope. Two always works. Case closed.

Could the answer be $1$ when neither divides the other? Also nope. With one move, only one number changes, so the changed number must become exactly the unchanged number. That requires divisibility. No divisibility, no one-move magic.

Therefore the minimum is:

$$\begin{cases} 0 & \text{if } a = b \\ 1 & \text{if } a \mid b \text{ or } b \mid a \\ 2 & \text{otherwise} \end{cases}$$

Complexity

Each test case uses only a couple modulo checks.

Time complexity: $O(1)$ per test case.

Memory complexity: $O(1)$.

Brutally small. The intended solution is basically just not tripping over the statement.