题目题解

问题理解

机器人从 $(a, b)$ 出发，每次可以选择 $dx, dy \in [0, k]$，移动到 $(x - dx, y - dy)$。
使用新的 $(dx, dy)$ 成本为 $1$，重复使用成本为 $0$。
求到达 $(0, 0)$ 的最小总成本。

---

第一步：平凡上界

总是可以使用操作 $(0, 1)$ 重复 $b$ 次，以及操作 $(1, 0)$ 重复 $a$ 次。
这两组操作各首次使用时成本 $1$，后续重复成本 $0$。
因此总成本 $\le 2$。

所以答案只可能是 $1$ 或 $2$。

---

第二步：何时成本为 $1$？

成本为 $1$ 意味着只使用一种 $(dx, dy)$ 对，重复若干次（可能一次）。
设使用 $t$ 次操作，则：

$$a = t \cdot dx, \quad b = t \cdot dy.$$

因此 $t$ 必须是 $a$ 和 $b$ 的公因数，且：

$$dx = \frac{a}{t} \le k, \quad dy = \frac{b}{t} \le k. $$

要存在这样的 $t$，等价于存在一个公因数 $t$ 使得 $\frac{a}{t} \le k$ 且 $\frac{b}{t} \le k$。

---

第三步：最大化 $t$

条件等价于：

$$t \ge \frac{a}{k} \quad \text{且} \quad t \ge \frac{b}{k}. $$

因此 $t$ 至少为 $\max\left(\left\lceil \frac{a}{k} \right\rceil, \left\lceil \frac{b}{k} \right\rceil\right)$。
同时 $t$ 必须是 $a$ 和 $b$ 的公因数。

显然，选择最大的可能 $t$（即 $g = \gcd(a, b)$）最有可能满足条件。
因为若存在某个 $t$ 满足条件，则 $g$ 是 $t$ 的倍数，$\frac{a}{g} \le \frac{a}{t} \le k$ 也成立。
所以只需检查 $g$ 即可。

---

第四步：判断条件

计算 $g = \gcd(a, b)$。
若

$$\frac{a}{g} \le k \quad \text{且} \quad \frac{b}{g} \le k, $$

则可以用 $(a/g, b/g)$ 重复 $g$ 次，成本为 $1$。
否则成本为 $2$。

---

第五步：时间复杂度

• 计算 $\gcd$：$O(\log \min(a, b))$。
• 总复杂度 $O(t \log \max(a, b))$，满足 $t \le 10^4$，$a,b \le 10^{18}$。

---

代码实现

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

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        ll a, b, k;
        cin >> a >> b >> k;
        
        // 使用 __gcd 或 std::gcd
        ll g = __gcd(a, b);  // GCC 内置函数，兼容性好
        // 或者使用 std::gcd 需要 C++17 和 <numeric>
        // ll g = gcd(a, b);
        
        if (a / g <= k && b / g <= k) {
            cout << "1\n";
        } else {
            cout << "2\n";
        }
    }
    
    return 0;
}

---

验证样例

输入：

4
3 5 15
2 3 1
12 18 8
9 7 5

输出：

1
2
1
2

与题目输出一致。

---

总结

本题的关键在于：

1. 观察到答案不超过 $2$。
2. 成本为 $1$ 当且仅当 $\gcd(a, b)$ 对应的操作步长不超过 $k$。
3. 只需检查 $\gcd(a, b)$ 即可，无需枚举所有公因数。