ZOJ 3593 One Person Game 【带简单处理的扩展欧几里得】

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3593

题意：给定一维坐标的出发点的终点，每次可以向左或向右走a,b或a+b的距离，问是否可达，如可达求最小步数

分析：这种每步有多种决策，初始感觉可能是DP，然而这个数据大小已经覆盖了整个int的大小，dp显然不现实。考虑到最终总是要求最小步数，某个对于a,b这两种步长最终肯定是只会分别沿着一个方向走的，因此我们先假设只有a,b两种步长可以选择，那么可以用扩展欧几里得求解。求出通解后，考虑到同方向的n个a步长和n个b步长可以合并为n个a+b步长，最终的步长也就是a与b分别步数的最大值；而方向相反的话，就是两个相加。根据线性二元不定方程的解的结构可以知道，以上两种情况要求最小步数，都是在两个步长步数相等的附近取得最小值。

AC代码：

//ZJU-3593 One Person Game
//AC 2016-4-18 20:15:03
//extent Euclid
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <list>
#include <climits>
#include <sstream>
#include <stack>
using namespace std;

#define cls(x) memset(x,0,sizeof x)
#define inf(x) memset(x,0x3f,sizeof x)
#define neg(x) memset(x,-1,sizeof x)
#define ninf(x) memset(x,0xc0,sizeof x)
#define st0(x) memset(x,false,sizeof x)
#define st1(x) memset(x,true,sizeof x)
#define INF 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define bug cout<<"here"<<endl;
//#define debug

long long X,Y;
long long extgcd(long long a,long long b)
{
    if(b==0)
    {
        X=1;
        Y=0;
        return a;
    }
    long long ans=extgcd(b,a%b);
    long long temp=Y;
    Y=X-(a/b)*Y;
    X=temp;
    return ans;
}

int main()
{
    #ifdef debug
        freopen("E:\Documents\code\input.txt","r",stdin);
        freopen("E:\Documents\code\output.txt","w",stdout);
    #endif
    int T;
    long long A,B,a,b;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld %lld %lld %lld",&A,&B,&a,&b);
        long long gcd=abs(extgcd(a,b));
        if((B-A)%gcd)
        {
            printf("-1
");
            continue;
        }
        long long t=abs((B-A)/gcd);
        X*=t;
        Y*=t;
        long long sa=abs(b/gcd),sb=abs(a/gcd);
        long long k=(Y-X)/(sa+sb);
        long long res=(long long)INF*(long long)INF;
        long long L=0,R=0;
        for(long long i=-1;i<=1;++i)
        {
            L=X+(k+i)*sa;
            R=Y-(k+i)*sb;
            if((L>=0&&R>=0)||(L<=0&&R<=0))
                res=min(res,max(abs(L),abs(R)));
            else
                res=min(res,abs(L)+abs(R));
        }
        printf("%lld
",res);
    }
    return 0;
}