ZOJ - 3593 One Person Game (扩展欧几里得) - Java

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：一个人在坐标A，要前往坐标B的位置。可以往左或往右走a，b，a+b个单位，求到达B的最小步数。

分析：扩展欧几里得算法求解线性方程的套路不变。令C=fabs(A-B),c = a+b, 扩展gcd分别求 ax+by=C ; ax+cy = C : bx+cy = C的最小|x|+|y|。求min{|x|+|y|}需要一点思考。

对于线性方程ax+by=c，设d = gcd(a,b) ,若方程有解，则必须d | c，特解为 (x0,y0) = ( xx*c/d，yy*c/d) 。设am = a/d, bm = b/d。

此时方程的通解为 x = x0+ k*bm ; y = y0 - k*am。则需要求的是 res = min{ |x0 + k*bm| + |y0 - k*am| }。

设直线L1：y1 = x0 + bm*k ； L2：y2 = y0 - am*k。

则|y1|+|y2| 的最小值一定出现在y1=0或y2=0，即k1=-x0/bm 或 k2 = y0/am 时（数形结合），但由于k是整数，所以不一定y1、y2能取到0。所以枚举区间[-x0/bm-1, -x0/bm+1]和[y0/am -1 , y0/am +1]的 k 对应值中的最小值。

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

typedef long long LL;

const int maxn = 1e5+;

LL ABS(LL a)

{

    return a>=?a :-a;

}

LL Exgcd(LL a,LL b,LL &x,LL &y ) {

    if ( b ==  ) {

        x = ;

        y = ;

        return a;

    }

    LL d = Exgcd(b, a%b, x, y), temp = x;

    x = y;

    y = temp-a/b*y;

    return d;

}

LL gao(LL a,LL b,LL c)          //ax+by=c

{

    LL x,y;

    LL d = Exgcd(a,b,x,y);

    if(c%d)  return -;

    LL am = a/d, bm = b/d;

    x *=c/d, y*= c/d;           //特解

    LL ans= ABS(x)+ABS(y);

    for(int i=-x/bm-;i<=-x/bm+;i++){

        LL X=x+bm*i;

        LL Y=y-am*i;

        if(i){

            LL tmp=ABS(X)+ABS(Y);

            if(tmp<ans) ans=tmp;

        }

    }

    for(int i=y/am-;i<=y/am+;i++){

        LL X=x+bm*i;

        LL Y=y-am*i;

        if(i){

            LL tmp=ABS(X)+ABS(Y);

            if(tmp<ans) ans=tmp;

        }

    }

    return ans;

}   

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    LL a,b,A,B,k;

    int T; scanf("%d",&T);

    while(T--){

        scanf("%lld %lld %lld %lld",&A, &B, &a, &b);

        LL C = ABS(A-B),c = a+b;

        LL t1 =gao(a,b,C), t2 = gao(a,c,C) ,t3 = gao(b,c,C);

        if(t1==- && t2==- && t3==-){

            puts("-1");

            continue;

        }

        LL ans=;

        if(t1!=-) ans = min(t1,ans);

        if(t2!=-) ans = min(t2,ans);

        if(t3!=-) ans = min(t3,ans);

        printf("%lld\n",ans);

    }

    return ;

}