📝 题目大意

给定两个整数 $A, B$，每次操作将较大的数减去较小的数（若 $A>B$ 则 $A \leftarrow A-B$，否则 $B \leftarrow B-A$），求使 $A=B$ 所需的最少操作次数。

💡 解题思路

1. 题目分析：直接模拟每次减一次会超时，因为 $A, B$ 最大可达 $10^{18}$，最坏情况（如 $A=10^{18}, B=1$）需要 $10^{18}$ 次操作。需要批量处理连续的减法操作。

2. 算法推导：

   • 本题本质是辗转相减法求 GCD 的过程，操作次数即辗转相减的步数。
   • 当 $A > B$ 时，我们可以连续减去多个 $B$，直到 $A \le B$。设 $k = \lfloor \frac{A-1}{B} \rfloor$，表示在 $A$ 仍大于 $0$ 的前提下最多能减多少次 $B$——减完 $k$ 次后 $A$ 要么小于 $B$，要么等于 $B$（此时循环终止）。
   • 将 $k$ 累加到答案 ans 中，然后更新 $A \leftarrow A - k \times B$。
   • 对称地，当 $B > A$ 时，$k = \lfloor \frac{B-1}{A} \rfloor$，ans += k，$B \leftarrow B - k \times A$。
   • 循环直到 $A = B$，输出 ans。
   • 之所以用 $(A-1)/B$ 而非 $A/B$，是因为 $A/B$ 在 $A$ 是 $B$ 的倍数时会多减一次导致 $A$ 变为 $0$（例如 $A=6, B=3$，$A/B=2$ 会直接让 $A=0$ 跳过 $A=B$ 的状态），而 $(A-1)/B$ 保证减完后 $A > 0$。

3. 边界与细节：

   • 初始 $A = B$ 时，操作次数为 $0$，循环不进入，直接输出 $0$。
   • 代码中的 if (A == 0 || B == 0) break; 是防御性写法，正常情况下正整数输入不会出现 $0$。
   • 变量使用 long long（64 位整数），因为 $A, B \le 10^{18}$ 且答案可能很大（最大约 $10^{18}$ 级别）。

⏱️ 复杂度分析

• 时间复杂度：$O(\log \max(A, B))$，与辗转相除法（欧几里得算法）同阶，每次批量减法相当于一次取模运算。
• 空间复杂度：$O(1)$，仅使用常数个变量。

💻 标准代码 (C++)

#include <iostream>
using namespace std;
int main() {
    long long A, B;
    cin >> A >> B;
    long long ans = 0;
    while (A != B) {
        // 防御性判断：若出现 0 则退出（正常情况不会到达）
        if (A == 0 || B == 0) break;
        if (A > B) {
            // 计算 A 可以连续减去多少个 B（保证减完后 A > 0）
            long long k = (A - 1) / B;
            ans += k;          // 累加操作次数
            A -= k * B;        // 批量减去 k 个 B
        } else {
            // 对称处理 B > A 的情况
            long long k = (B - 1) / A;
            ans += k;
            B -= k * A;
        }
    }
    cout << ans << endl;
    return 0;
}