记录编号	605966	评测结果	AAAAAAAAAAAA
题目名称	4177.[USACO25 Feb Silver]Transforming Pairs	最终得分	100
用户昵称	汐汐很希希	是否通过	通过
代码语言	C++	运行时间	0.192 s
提交时间	2025-09-13 14:35:14	内存使用	3.66 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=110;
const int M=2010;
const int MOD=998244353;
int T;
int main()
{
    freopen("Transforming.in","r",stdin);
    freopen("Transforming.out","w",stdout);
    
    cin>>T;
    while(T)
    {
        T--;
        ll a,b,c,d;
        cin>>a>>b>>c>>d;
        ll ans=0;
        if(c<a||d<b){
            cout<<-1<<endl;
            continue;
        }else if(c==a&&d==b){
            cout<<0<<endl;
            continue;
        }
        bool flag=true;
        while(c!=a||d!=b){
            if(c<a||d<b){
                cout<<-1<<endl;
                flag=false;
                break;
            }
            if(c>=d){
                ll t=(c-a)/d;
                ans+=max(t,1ll);
                c-=max(t,1ll)*d;
            }else if(c<d){
                ll t=(d-b)/c;
                ans+=max(t,1ll);
                d-=max(t,1ll)*c;
            }
        }
        if(flag) cout<<ans<<endl;
    }
    return 0;
}