题目描述

聪明奶牛 Bessie 发现了一种新的迷恋——数学魔法！一天，当她在 Farmer John 牧场的草地上小跑时，她偶然发现了两堆有魔法的干草。第一堆包含 aa 捆干草，第二堆包含 bb 捆干草（1≤a,b≤10181≤a,b≤1018）。

在干草堆边上，半埋在泥土里，她发现了一卷古老的卷轴。当她展开卷轴时，发光的字母揭示了一个预言：

奉大草原之令，被选中者需令此平凡之干草堆转为恰好 cc 捆及 dd 捆——不可多，亦不可少。

Bessie 意识到她只能施展以下两种魔法：

• 她可以施法召唤新的干草捆以增加第一堆的大小，增加的数量等于当前第二堆的数量。
• 她可以施法召唤新的干草捆以增加第二堆的大小，增加的数量等于当前第一堆的数量。

她必须逐次执行这些操作，但可以任意顺序执行任意多次。她必须恰好使第一堆达到 cc 捆，第二堆达到 dd 捆（1≤c,d≤10181≤c,d≤1018）。

对于 TT（1≤T≤1041≤T≤104）个独立的测试用例中的每一个，输出实现预言所需的最小操作次数，或者如果不可能实现时输出 -1。

输入格式

输入的第一行包含 TT。

以下 TT 行，每行包含四个整数 aa，bb，cc，dd。

输出格式

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

输入输出样例 #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>db>d，但操作只可能增加 bb，因此不可能实现。

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

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

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

• 测试点 3∼43∼4：max⁡(c,d)≤20⋅min⁡(a,b)max(c,d)≤20⋅min(a,b)。
• 测试点 5∼75∼7：T≤10T≤10 且 a,b,c,d≤106a,b,c,d≤106。
• 测试点 8∼128∼12：没有额外限制。

思路

直接数学枚举即可。

代码见下

#include<bits/stdc++.h>
using namespace std;
long long t,a,b,c,d,op=0;
int main(){
//	freopen("Pairs.in","r",stdin);
//	freopen("Pairs.out","w",stdout);
	cin>>t;
	while(t--){
		cin>>a>>b>>c>>d;
		op=0;
		while(a!=c||b!=d){
			if(d-b>=c){
				op+=((d-b)/c);
				d=d-c*((d-b)/c);
			}
            else if(c-a>=d){
				op+=((c-a)/d);
				c=c-d*((c-a)/d);
			}
            else{
				op=-1;
				break;
			}
		}
		cout<<op<<endl;
	}
	return 0;
}