CF1538D Another Problem About Dividing Numbers

给定两个整数 $a$ 和 $b$。每次操作，你可以进行以下两种操作之一： - 选择一个整数 $c$（$c > 1$ 且 $a$ 能被 $c$ 整除），用 $\frac{a}{c}$ 替换 $a$； - 选择一个整数 $c$（$c > 1$ 且 $b$ 能被 $c$ 整除），用 $\frac{b}{c}$ 替换 $b$。 你的目标是用恰好 $k$ 次操作使 $a$ 和 $b$ 相等。 例如，$a=36$ 和 $b=48$ 可以在 $4$ 步内变为相等： - $c=6$，将 $b$ 除以 $c$，得到 $a=36$，$b=8$； - $c=2$，将 $a$ 除以 $c$，得到 $a=18$，$b=8$； - $c=9$，将 $a$ 除以 $c$，得到 $a=2$，$b=8$； - $c=4$，将 $b$ 除以 $c$，得到 $a=2$，$b=2$。 对于给定的 $a$ 和 $b$，判断是否可以用恰好 $k$ 次操作使它们相等。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）。接下来有 $t$ 组测试数据。 每组测试数据包含三个整数 $a$、$b$ 和 $k$（$1 \le a, b, k \le 10^9$）。

对于每组测试数据，输出一行： - 如果可以用恰好 $k$ 次操作使 $a$ 和 $b$ 相等，输出 "Yes"； - 否则输出 "No"。 "Yes" 和 "No" 的大小写不限。

由 ChatGPT 4.1 翻译