比赛 2025.9.13 评测结果 AAAAAAAAAAAA
题目名称 Transforming Pairs 最终得分 100
用户昵称 xxz 运行时间 0.150 s
代码语言 C++ 内存使用 3.79 MiB
提交时间 2025-09-13 10:56:42
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,a,b,c,d,op1,op2,flag,k,ans;
int tp(int a,int b,int c,int d){
	if(a>c||b>d){
		return -1;
	}
	if(a>c&&b==d||b>d&&a==c){
		return -1;
	}
	if(a==c&&b==d)return 0;
	return -2;
}
void dfs(int x,int y,int step){
	if(x==c&&y==d){
		cout<<step<<endl;
		flag=1;
		return;
	}
	if(tp(x+y,y,c,d)!=-1){
		dfs(x+y,y,step+1);
	}
	if(tp(x,x+y,c,d)!=-1){
		dfs(x,x+y,step+1);
	}
	return;
}
struct node{
	int x,y,step;
}p;

int bfs(int x,int y){
	flag=0;
	int ans=0;
	queue<node>q;
	q.push({x,y,0});
	while(!q.empty()){
		p=q.front();q.pop();
		if(tp(p.x,p.y,c,d)==0){
			ans=p.step;
			flag=1;
			break;
		}
		if(tp(p.x+p.y,p.y,c,d)!=-1){
			q.push({p.x+p.y,p.y,p.step+1});
		}
		if(tp(p.x,p.x+p.y,c,d)!=-1){
			q.push({p.x,p.x+p.y,p.step+1});
		}
	}
	return ans;
}
void solve(){
	while(a!=c||b!=d){
		if(c<a||d<b){
			ans=-1;break;
		}
		if(c<d){
			swap(c,d);
			swap(a,b);
		}
		k=(c-a)/d;
		ans+=k;
		c-=max(k,1ll)*d;
	}
	return;
}
signed main(){
	freopen("Transforming.in","r",stdin);freopen("Transforming.out","w",stdout);
	cin>>t;
	while(t--){
		ans=0;
		flag=0;
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		// if(!tp(a,b,c,d)){
		// 	cout<<0<<endl;
		// 	continue;
		// }else if(tp(a,b,c,d)==-1){
		// 	cout<<-1<<endl;
		// 	continue;
		// }
		// int y=bfs(a,b);
		// if(!flag)cout<<-1<<endl;
		// else cout<<y<<endl;
		solve();
		cout<<ans<<endl;
	}
	return 0;
}