题目

ak47

题意

在数轴上有两个点 A B（给出坐标），还告诉你 a，b

表示可以向左或向右走 a 或 b 或者走 a+b

6 种走法 走一次算一步

问从 A 走到 B 最少要多少步。

题解

容易想到方程 ax+by=c

x 表示用 a 走了多少次 y 表示用 b 走了多少次

这样用扩展 gcd 可以求出一组解和解的取值范围 同时可以判断是否有解（c%gcd(a,b)==0?）

假如 x y 同号 ans=min(abs(x),ans(y))(因为可以一次走 (a+b)); 异号 ans=abs(x)+abs(y);

x y 的取值范围 在直角坐标系上是两条直线 且斜率一正一负 在交点处取最优值

但是交点有可能是小数 那么就枚举交点周围的几个值 取最小值

程序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll _gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll res=_gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;y=tmp-a/b*y;
    return res;
}
ll get(ll a,ll b){
    if(a*b<0)return abs(a)+abs(b);
    else return abs(a)>abs(b)?abs(a):abs(b);
}
int main(){
    freopen("a.in","r",stdin);
    int t;scanf("%d",&t);
    ll a,b,A,B;
    while(t--){
        scanf("%lld%lld%lld%lld",&A,&B,&a,&b);
        ll c=abs(A-B),x,y,g=_gcd(a,b,x,y);
        if(c%g){
            printf("-1\n");
            continue;
        }
        a/=g;b/=g;
        x*=(c/g);y*=(c/g);
        double t=(y-x)*1.0/(a+b);
        ll k=t;
        ll ans=get(x+k*b,y-a*k);
        k++;ans=min(ans,get(x+k*b,y-a*k));
        k++;ans=min(ans,get(x+k*b,y-a*k));
        k-=3;ans=min(ans,get(x+k*b,y-a*k));
        k--;ans=min(ans,get(x+k*b,y-a*k));
        printf("%lld\n",ans);
    }
    return 0;
}