Transforming Pairs

题目描述

聪明绝顶的奶牛 Bessie 发现了一种新的爱好——数学魔法！一天，她在 Farmer John 牧场的田野里小跑时，偶然遇到了两堆被施了魔法的干草。第一堆有 $a$ 捆，第二堆有 $b$ 捆（$1\le a,b\le 10^{18}$）。 在干草旁边，她在泥土里半埋着发现了一张古老的卷轴。她将其展开时，发光的文字显现出一则预言： 为了遵从伟大草原的法令，被选中者必须把这两堆不起眼的干草变为恰好 $c$ 捆和 $d$ 捆——不多不少。 Bessie 意识到她只能施展以下两种法术： 她可以凭空变出新的草捆，使第一堆的数量增加“当前第二堆的数量”。 她可以凭空变出新的草捆，使第二堆的数量增加“当前第一堆的数量”。 她必须按顺序逐次执行这些操作，但可以以任意次数、任意顺序执行。她必须最终使第一堆恰好为 $c$ 捆、第二堆恰好为 $d$ 捆（$1\le c,d\le 10^{18}$）。 对于 $T$ 个（$1\le T\le 10^4$）相互独立的测试用例，输出满足预言所需的最少操作次数；若不可能做到，输出 -1。

输入格式

第一行包含 $T$。 接下来 $T$ 行每行包含四个整数 $a,b,c,d$。

输出格式

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

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

-1
3
-1
0

1
1 1 1 1000000000000000000

999999999999999999

提示

在第一个测试用例中，这是不可能的，因为初始时 $b>d$，但操作只能增加 $b$。 在第二个测试用例中，初始两堆为 $(5, 3)$ 捆。Bessie 可以先将第一堆增加第二堆的数量，得到 $(8, 3)$ 捆。然后她可以将第二堆增加第一堆的新数量，并将该操作执行两次，依次得到 $(8, 11)$，最终得到 $(8, 19)$ 捆。这与 $c$ 和 $d$ 匹配，并且是到达该状态所需的最少操作次数。 注意第三个测试用例与第二个答案不同，因为 $c$ 与 $d$ 互换了（两堆的顺序是重要的）。 在第四个测试用例中，不需要任何操作。 SCORING: Inputs 3-4: $\max(c, d) \le 20 \cdot\min(a, b)$ Inputs 5-7: $T \le 10$ and $a,b,c,d\le 10^6$ Inputs 8-12: No additional constraints Problem credits: Benjamin Qi

标签: USACO|2025|Silver

来源

USACO|2025|Silver