题目分析

我们有一个对整数对 $(a,b)$ 的操作：

1. $a \mathrel{+}= b$（将 $a$ 加上 $b$）
2. $b \mathrel{+}= a$（将 $b$ 加上 $a$）

需要将 $(a,b)$ 变为 $(c,d)$，求最小操作次数，无法完成则输出 $-1$。

---

核心思路

1. 问题转化

操作可以看作矩阵乘法：

• $a \mathrel{+}= b$：$\begin{pmatrix}1&1\\0&1\end{pmatrix} \begin{pmatrix}a\\b\end{pmatrix}$
• $b \mathrel{+}= a$：$\begin{pmatrix}1&0\\1&1\end{pmatrix} \begin{pmatrix}a\\b\end{pmatrix}$

这两个矩阵行列式均为 $1$，因此变换不改变最大公约数：

$$\gcd(a,b) = \gcd(c,d)$$

这是有解的必要条件。

---

2. 逆向思考

从 $(c,d)$ 逆推操作：

• 如果 $c > d$，最后一步可能是 $a \mathrel{+}= b$ 的逆操作：$c \to c-d$，$d$ 不变
• 如果 $c < d$，最后一步可能是 $b \mathrel{+}= a$ 的逆操作：$d \to d-c$，$c$ 不变

这与辗转相除法完全相同：不断用大的减去小的，直到得到 $(a,b)$。

---

3. 符号处理

关键难点：$a,b,c,d$ 可能为负数。

观察：

• 如果 $a$ 和 $b$ 同号，可以通过操作保持符号不变
• 如果 $a$ 和 $b$ 异号，操作可能改变符号

代码通过分类讨论处理符号问题：

1. 同号情况：化为非负处理
2. 异号情况：需要特殊处理可能跨越坐标轴的情况

---

算法设计

1. 核心函数 gcd(a,b,c,d)

计算当 $a,b \ge 0$ 时的最小步数：

int gcd(int a, int b, int c, int d) {
    if (c < 0 || d < 0) return -1;  // 目标不能有负数
    if (a == c && b == d) return 0;
    
    int res = 0;
    while (c != 0 && d != 0) {
        if (a == c && b == d) return res;
        if (c == d) {  // 特殊情况处理
            if ((a == 0 && b == d) || (b == 0 && a == c)) 
                return res + 1;
            return -1;
        }
        if (c < d) swap(c, d), swap(a, b);
        
        // 快速检查能否直接到达
        if (b == d && c >= a && c % d == a % d) 
            return res + (c - a) / d;
        
        // 欧几里得步骤
        res += c / d;
        c %= d;
    }
    return (a == c && b == d) ? res : -1;
}

---

2. 主算法流程

情况 1：$a,b$ 同号

• 化为非负情况，直接调用 gcd 函数

情况 2：$a,b$ 异号，$c,d$ 异号

• 如果符号模式不匹配，直接返回 $-1$
• 否则通过交换和取负转化为情况 1

情况 3：$a,b$ 异号，$c,d$ 同号（最复杂）

1. 预计算：从 $(c,d)$ 逆推到坐标轴的所有可能路径
2. 枚举：$(a,b)$ 走到坐标轴的不同方式
3. 匹配：找到最短的拼接路径

---

3. 优化技巧

预计算目标路径

vector<array<int, 3>> q;
for (int x = c, y = d, num = 0; x > 0 && y > 0;) {
    if (y >= x) num += y / x, y %= x;
    else q.push_back({y, x, num}), num += x / y, x %= y;
}

存储从 $(c,d)$ 逆推到每个中间状态的信息。

快速跳过

利用整数除法一次性减去多个倍数，将复杂度从 $O(\text{值域})$ 降为 $O(\log(\max))$。

---

复杂度分析

• gcd 函数：$O(\log(\max(c,d)))$
• 路径枚举：$O(\log^2(\max))$
• 总复杂度：$O(Q \log^2 M)$，其中 $M = \max(|a|,|b|,|c|,|d|)$

对于 $Q \le 10^5$ 可接受。

---

样例验证

样例 1

输入：5 -3 -1 -3
处理：
1. (5,-3) → (2,-3)   [a+=b]
2. (2,-3) → (-1,-3)  [a+=b]
输出：2

样例 2

输入：5 3 5 2
gcd(5,3) = 1, gcd(5,2) = 1，但无法通过操作从 (5,3) 到 (5,2)
输出：-1

样例 3

输入：5 3 8 19
步骤：
1. (5,3) → (8,3)    [a+=b]
2. (8,3) → (8,11)   [b+=a]  
3. (8,11) → (8,19)  [b+=a]
输出：3

---

关键性质

1. 不变量：$\gcd$ 保持不变
2. 可逆性：操作可逆，可用逆向思维
3. 符号对称：可通过取负和交换简化情况
4. 欧几里得结构：本质是扩展欧几里得算法的变形

---

算法标签

• 数论 (Number Theory)
• 辗转相除法 (Euclidean Algorithm)
• 分类讨论 (Case Analysis)
• 逆向思维 (Reverse Thinking)

---

总结

本题通过分析操作的不变量和可逆性，将问题转化为经典数论问题。核心在于处理负数情况的分类讨论，以及利用欧几里得算法的快速计算。对于最复杂的异号转同号情况，通过预计算目标路径和枚举起始路径的方式找到最优解。