ZOJ 3593 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步或b或c步，c=a+b;问最小步数；

根据公式ax+by=c;，当x,y同号时等于max（x,y）,当a,b异号时等于（abs(x)+abs(y)）,因为a,b大于0，所以不管x,y同号还是异号都是当x,y,最接近时，答案最小，写出通式

x=x1+b/(gcd)*k,y=y1-a/gcd*k; 假设x,y相等,k=(y-x)/(a+b),因为x,y不一定相等,所以枚举k附近的点

大意：一维坐标轴，有A和B两个地方，现在从A到B，每次可以向任意方向走a、b或者c的距离，其中c=a+b，问能不能走到B，能的话最少走几次。

 

首先可以推出这个式子：a*x+b*y+c*z=|B-A|然后又因为c=a+b，所以其实可以化成a*x+b*y=|B-A|。所以需要用扩展gcd求出x,y,但是这个x,y有可能不是最优的，为什么呢？为了让步数最小就要拉近x，y的距离，使|x-y|最小。怎么拉近，

下面来看通解方程：

 

 x = x0 + (b/gcd)*t

 y = y0 – (a/gcd)*t 

实际上是关于x,y关于t的两条直线（他们必有交叉点）。

可以设x==y，然后解出那个对应的t

,得到此时的一组解（t=(y0-x0)/((a+b)/gcd)）但是实际上有可能无法使x==y（没有整数t)，所以算出来的t接近于交叉点的t(有可能是小数)，所以可能也不是最优解，所以需要增加一次t+1，t-1，这样比较3个t得到的结果（x,y同为正或同为负时，绝对值大的那个值（c的存在，a和b合并为c），一正一负就是绝对值和），其中小的一个必是最优解。

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <string>  
#include <vector>  
#include <stack>  
#include <queue>  
#include <algorithm>  

#define INF 0x7fffffff  
#define EPS 1e-12  
#define MOD 100000007  
#define PI 3.14159265357979823846  
#define N 100005  

using namespace std;

typedef long long ll;

ll e_gcd(ll a, ll b, ll &x, ll &y)
{
    ll d = a;
    if (b != 0)
    {
        d = e_gcd(b, a%b,y, x);
        y = y - a / b * x;
    }
    else
    {
        x = 1; y = 0;
    }
    return d;
}

ll cal(ll a, ll b, ll l)
{
    ll x, y;
    ll gcd = e_gcd(a, b, x, y);
    if (l%gcd != 0) return -1;
    x *= l / gcd;
    y *= l / gcd;
    a = a / gcd;
    b = b / gcd;
    ll ans = ((ll)INF)*((ll)INF), f;
    //下面来看通解方程：
    //    x = x0 + (b / gcd)*t
    //    y = y0 –(a / gcd)*t
    //    实际上是关于x, y关于t的两条直线（他们必有交叉点）。
    //    可以设x == y，然后解出那个对应的t
    //    , 得到此时的一组解（t = (y0 - x0) / ((a + b) / gcd)）
    //但是实际上有可能无法使x == y（没有整数t)
    ll mid = (y - x) / (a + b); 
    for (ll T = mid - 1; T <= mid + 1; T++)
    {
        // 当x, y同号时等于max（x, y）,先走几步（a+b）的，再走几步单独的
        if (abs(x + b * T) + abs(y - a * T) == abs(x + b * T + y - a * T))
            f = max(abs(x + b * T), abs(y - a * T));
        else//当a,b异号时等于（abs(x)+abs(y)）
            f = fabs(x - y + (a + b)*T);
        ans = min(ans, f);
    }
    return ans;
}

int main()
{
    ll A, B, a, b, x, y;
    int t;
    cin >> t;
    while (t--)
    {
        cin >> A >> B >> a >> b;
        ll l = B - A;
        ll ans = cal(a, b, l);
        if (ans == -1) cout << "-1"<<endl;
        else cout << ans << endl;
    }
    return 0;
}