题目回顾

A. 枫树与乘法
每次测试时间限制：$1$ 秒
每次测试内存限制：$256$ 兆字节

枫树有两个正整数 $a$ 和 $b$。她可以执行任意多次（可能为零次）如下操作，使得 $a$ 等于 $b$：

• 选择任意正整数 $x$，并将 $a$ 或 $b$ 乘以 $x$。

求最少操作次数。可以证明答案总是存在。

输入：$t$ 个测试用例，每个用例一行两个整数 $a, b$（$1 \le a, b \le 1000$）。
输出：每个用例一行，最少操作次数。

---

题解

情况一：$a = b$

此时两数已经相等，不需要任何操作。

$$\text{答案} = 0$$

---

情况二：一个数能被另一个数整除

假设 $a$ 能被 $b$ 整除，即 $a \bmod b = 0$。
那么我们可以选择 $x = \frac{a}{b}$，将 $b$ 乘以 $x$，得到：

$$b \times \frac{a}{b} = a$$

一次操作后 $b$ 变为 $a$，两数相等。
同理，如果 $b$ 能被 $a$ 整除，一次操作将 $a$ 乘以 $\frac{b}{a}$ 即可。

因此：

$$\text{答案} = 1 \quad \text{当} \quad a \mid b \ \text{或} \ b \mid a \ \text{且} \ a \ne b $$

其中 $a \mid b$ 表示 $a$ 整除 $b$。

---

情况三：其他情况（互不整除）

此时一次操作无法完成，因为：

• 若只动 $a$ 使其等于 $b$，需要 $b/a$ 为整数，但 $a \nmid b$；
• 若只动 $b$ 使其等于 $a$，需要 $a/b$ 为整数，但 $b \nmid a$。

但是两次操作总是可行的。
我们取 $m = a \times b$，然后：

1. 将 $a$ 乘以 $b$，得到 $a \times b$；
2. 将 $b$ 乘以 $a$，得到 $a \times b$。

两次操作后，两个数都等于 $a \times b$。

因此：

$$\text{答案} = 2 \quad \text{当} \quad a \nmid b \ \text{且} \ b \nmid a $$

---

最终分段函数

综合以上三种情况：

$$\boxed{ \text{答案} = \begin{cases} 0, & a = b \\[4pt] 1, & a \mid b \ \text{或} \ b \mid a \ \text{且} \ a \ne b \\[4pt] 2, & \text{否则} \end{cases} } $$

---

复杂度分析

每个测试用例只需进行 $O(1)$ 次整除判断，总时间复杂度 $O(t)$，空间复杂度 $O(1)$，完全满足 $t \le 100$ 的限制。

---

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int solve() {
    int a, b;
    cin >> a >> b;
    if (a == b) return 0;
    if (a % b == 0 || b % a == 0) return 1;
    return 2;
}

int main() {
    ios::sync_with_stdio(false);
    int TC;
    cin >> TC;
    while (TC--) {
        cout << solve() << '\n';
    }
    return 0;
}

---

示例验证

输入：

3
1 2
10 3
1000 1000

• $a=1, b=2$：$2$ 能被 $1$ 整除？不，是 $1$ 能被 $2$ 整除？否。但 $2 \bmod 1 = 0$ 吗？注意判断条件 a % b == 0 || b % a == 0：
  $1 \% 2 = 1 \ne 0$，$2 \% 1 = 0$，成立 → 输出 $1$ ✅
• $a=10, b=3$：$10 \% 3 = 1$，$3 \% 10 = 3$，都不为 $0$ → 输出 $2$ ✅
• $a=1000, b=1000$：相等 → 输出 $0$ ✅

输出：

1
2
0

与题目示例完全一致。