#PU1496. USACO 2025 February Contest, Silver — Problem 3. Transforming Pairs

USACO 2025 February Contest, Silver — Problem 3. Transforming Pairs

USACO 2025 February Contest, Silver — Problem 3. Transforming Pairs

题目描述

Bessie the brilliant bovine has discovered a new fascination—mathematical magic! One day, while trotting through the fields of Farmer John’s ranch, she stumbles upon two enchanted piles of hay. The first pile contains aa bales, and the second pile contains bb bales (1≤a,b≤10181\le a,b\le 10^{18}). Next to the hay, half-buried in the dirt, she discovers an ancient scroll. As she unfurls it, glowing letters reveal a prophecy: To fulfill the decree of the Great Grasslands, the chosen one must transform these two humble hay piles into exactly cc and dd bales—no more, no less. Bessie realizes she can only perform the following two spells: She can magically conjure new bales to increase the first pile’s size by the amount currently in the second pile. She can magically conjure new bales to increase the second pile’s size by the amount currently in the first pile. She must perform these operations sequentially, but she can perform them any number of times and in any order. She must reach exactly cc bales in the first pile and dd bales in the second pile (1≤c,d≤10181\le c,d\le 10^{18}). For each of TT (1≤T≤1041\le T\le 10^4) independent test cases, output the minimum number of operations needed to fulfill the prophecy, or if it is impossible to do so, output -1.

输入格式

The first line contains TT. The next TT lines each contain four integers a,b,c,da,b,c,d.

输出格式

(见题面原文)

数据范围

Inputs 3-4: max⁡(c,d)≤20⋅min⁡(a,b)\max(c, d) \le 20 \cdot\min(a, b) Inputs 5-7: T≤10T \le 10 and a,b,c,d≤106a,b,c,d\le 10^6 Inputs 8-12: No additional constraints Problem credits: Benjamin Qi

样例

样例 1

4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3
-1
3
-1
0
In the first test case, it is impossible since $b>d$ initially, but operations
can only increase $b$.
In the second test case, initially the two piles have $(5, 3)$ bales.  Bessie
can first increase the first pile by the amount in the second pile, resulting in
$(8, 3)$ bales.  Bessie can then increase the second pile by the new amount in
the first pile, and do this operation twice, resulting in $(8, 11)$ and finally
$(8, 19)$ bales.  This matches $c$ and $d$ and is the minimum number of
operations to get there.

样例 2

1
1 1 1 1000000000000000000
999999999999999999

提示

and dd are swapped (the order of the piles matters). In the fourth test case, no operations are necessary.