Divide and Conquer

Key Observation

Each operation divides the current value of $x$ by some divisor of it. That means the operation never introduces new prime factors, never increases $x$, and never does anything fancy. It only removes factors from $x$.

Suppose the original value is $x_0$. If we do several operations with chosen values $z_1, z_2, \dots, z_k$, then the final value is

$$\frac{x_0}{z_1 z_2 \cdots z_k}.$$

Because every chosen $z_i$ divides the current value at that moment, this product divides the original $x_0$. So the final number must be a divisor of the original $x$.

Therefore, if we want to end at $y$, we need:

$$y \mid x$$

or equivalently:

$$x \bmod y = 0.$$

Why This Is Also Sufficient

Now assume $y$ divides $x$. Then $x/y$ is an integer. Choose

$$z = \frac{x}{y}.$$

Since $y$ divides $x$, this $z$ divides $x$. After one operation:

$$x := \frac{x}{z} = \frac{x}{x/y} = y.$$

Done. One move. Clean.

Common Trap

Do not simulate all possible divisor choices. That is doing CrossFit for a doorbell problem. Since you are allowed to choose any divisor, the direct jump works whenever $y$ divides $x$.

Also, checking $x \le y$ is not enough. For example, $x = 6$, $y = 3$ works, but $x = 6$, $y = 4$ does not. The actual condition is divisibility.

Algorithm

For each test case:

1. Read $x$ and $y$.
2. If $x \% y == 0$, print YES.
3. Otherwise, print NO.

Correctness Proof

We prove that the algorithm prints YES exactly when it is possible to make $x$ equal to $y$.

First, suppose the algorithm prints YES. Then $x \% y = 0$, so $y$ divides $x$. Choose $z = x/y$. Since $z$ divides $x$, this is a valid operation. The new value becomes $x / z = y$, so it is possible to make $x$ equal to $y$.

Now suppose it is possible to make $x$ equal to $y$. Each operation divides the current value by one of its divisors, so every value produced remains a divisor of the original $x$. Therefore the final value $y$ must divide the original $x$. Hence $x \% y = 0$, so the algorithm prints YES.

Since both directions hold, the algorithm is correct.

Complexity

Each test case does one modulo operation.

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

Memory complexity: $O(1)$.