One Person Game（扩展欧几里德求最小步数）

One Person Game

Time Limit: 2 Seconds Memory Limit: 65536 KB

There is an interesting and simple one person game. Suppose there is a number axis under your feet. You are at point A at first and your aim is point B. There are 6 kinds of operations you can perform in one step. That is to go left or right by a,b and c, here c always equals to a+b.

You must arrive B as soon as possible. Please calculate the minimum number of steps.

Input

There are multiple test cases. The first line of input is an integer T(0 < T ≤ 1000) indicates the number of test cases. Then T test cases follow. Each test case is represented by a line containing four integers 4 integers A, B, a and b, separated by spaces. (-2³¹ ≤ A, B < 2³¹, 0 < a, b < 2³¹)

Output

For each test case, output the minimum number of steps. If it's impossible to reach point B, output "-1" instead.

Sample Input

2
0 1 1 2
0 1 2 4

Sample Output

1
-1

题解：不难列出线性方程a(x+z)+b(y+z)=B-A;即ax+by=C;

主要是中间找最小步数；//由于a+b可以用c来代替；所以，当x和y同号时， 34 //就可以用z=min(x,y)+max(x,y)-min(x,y)=max(x,y)来走,也就是一部分步数可以等于a+b 35 //所以还要找这种情况的步数。。。 36 //因为x和y越接近，（a+b）*step的越多，越优化， 37 //所以要在通解相交的点周围找；由于交点可能为小数，所以才在周围找的；

代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<vector>
 7 #define mem(x,y) memset(x,y,sizeof(x))
 8 using namespace std;
 9 typedef long long LL;
10 const int INF=0x3fffffff;
11 void e_gcd(LL a,LL b,LL &d,LL &x,LL &y){
12     if(!b){
13         d=a;
14         x=1;
15         y=0;
16     }
17     else{
18         e_gcd(b,a%b,d,x,y);
19         LL temp=x;
20         x=y;
21         y=temp-a/b*y;
22     }
23 }
24 LL cal(LL a,LL b,LL c){
25     LL x,y,d;
26      e_gcd(a,b,d,x,y);
27      //printf("%lld %lld %lld
",d,x,y);
28      if(c%d!=0)return -1;
29      x*=c/d;
30      y*=c/d;
31      //x=x0+b/d*t;y=y0-a/d*t;
32      b/=d;a/=d;
33      //由于a+b可以用c来代替；所以，当x和y同号时，
34      //就可以用z=min(x,y)+max(x,y)-min(x,y)=max(x,y)来走,也就是一部分步数可以等于a+b 
35      //所以还要找这种情况的步数。。。 
36      //因为x和y越接近，（a+b）*step的越多，越优化，
37      //所以要在通解相交的点周围找；由于交点可能为小数，所以才在周围找的；
38      LL mid=(y-x)/(a+b); // x0+bt=y0-at;
39      LL ans=(LL)INF*(LL)INF;
40      LL temp;
41     // printf("%lld
",ans);
42      for(LL t=mid-1;t<=mid+1;t++){
43          if(abs(x+b*t)+abs(y-a*t)==abs(x+b*t+y-a*t))
44          temp=max(abs(x+b*t),abs(y-a*t));
45          else temp=abs(x+b*t)+abs(y-a*t);
46          ans=min(ans,temp);
47      //    printf("%lld
",temp);
48      }
49      return ans;
50 }
51 int main(){
52     LL T,A,B,a,b;
53     scanf("%lld",&T);
54     while(T--){
55         scanf("%lld%lld%lld%lld",&A,&B,&a,&b);
56         LL ans=cal(a,b,B-A);
57         printf("%lld
",ans);
58     }
59     return 0;
60 }