P11841 [USACO25FEB] Transforming Pairs S

题目描述

给出四个整数 $a$，$b$，$c$，$d$ ,

每次操作执行： $a \gets a + b$ 或 $b \gets b + a$ ，

求至少需要多少次操作才能满足 $a=c$ 且 $b=d$ 。

如果不可能实现时输出 -1。

输入格式

输入的第一行包含 $T$。

以下 $T$ 行，每行包含四个整数 $a$，$b$，$c$，$d$（$1\le a,b,c,d\le 10^{18}$）。

输出格式

输出 $T$ 行，为每一个测试用例的答案。

输入输出样例 #1

输入 #1

4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3

输出 #1

-1
3
-1
0

输入输出样例 #2

输入 #2

1
1 1 1 1000000000000000000

输出 #2

999999999999999999

说明/提示

样例 1 解释：

在第一个测试用例中，由于 $b>d$，但操作只可能增加 $b$，因此不可能实现。

在第二个测试用例中，最初 $(a=5, b=3)$ 。Bessie 可以将第一堆增加第二堆的数量，得到 $(8, 3)$ 。然后 Bessie 可以将第二堆增加第一堆的新数量，并执行该操作两次，得到 $(8, 11)$ 并最后得到 $(8, 19)$ 。这与 $c$ 和 $d$ 一致，且是达到目标的最小操作次数。

注意，第三个测试用例的答案与第二个不同，因为 $c$ 和 $d$ 的值交换了（堆的顺序有影响）。

在第四个测试用例中，不需要任何操作。

• 测试点 $3\sim 4$：$\max(c, d) \le 20 \cdot\min(a, b)$。
• 测试点 $5\sim 7$：$T \le 10$ 且 $a,b,c,d\le 10^6$。
• 测试点 $8\sim 12$：没有额外限制。