学步园

一道变形的数论题，用到了扩展的欧几里德，具体看代码，另附上某大牛的解析：点击打开链接

题目

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
struct euclid
{
    LL x,y,d;
};
LL labs(LL x)
{
    if(x<0)return -x;
    return x;
}
euclid Euclid(LL a,LL b)
{
    euclid eld1;
    eld1.d=a;
    eld1.x=1;
    eld1.y=0;
    if(!b)return eld1;
    euclid eld2=Euclid(b,a%b);
    eld1.d=eld2.d;
    eld1.x=eld2.y;
    eld1.y=eld2.x-a/b*eld2.y;
    return eld1;
}
LL cal(LL a,LL b)
{
    LL aa=labs(a),bb=labs(b);
    if(a*b>0)return max(aa,bb);             //当a，b同号时，就取它们绝对值之中大的那个数
    return aa+bb;             //异号时，就是两个数绝对值的和
}
int main()
{
    //freopen("a.txt","r",stdin);
    int ca;
    scanf("%d",&ca);
    while(ca--)
    {
        LL s,t,a,b;
        scanf("%lld%lld%lld%lld",&s,&t,&a,&b);
        LL d=labs(s-t);
        euclid eld=Euclid(a,b);             //先用扩展的欧几里德判断是否有解
        if(d%eld.d)
        {
            printf("-1\n");
            continue;
        }
        eld.x*=d/eld.d;
        eld.y*=d/eld.d;
        LL k,x,y,step1,step2;
        if(eld.x>eld.y)
        {
            k=(eld.x-eld.y)/(a/eld.d+b/eld.d);
            x=eld.x-k*b/eld.d;
            y=eld.y+k*a/eld.d;             //求出当eld.x-k*（b/bel.d）=eld.y+k*（a/bel.d）的k值，因为当x==y时，x+y的值最小
            step1=cal(x,y);
            x-=b/eld.d;
            y+=a/eld.d;
            step2=cal(x,y);             //求出k值左右的两种情况
        }
        else
        {
            k=(eld.y-eld.x)/(a/eld.d+b/eld.d);
            x=eld.x+k*b/eld.d;
            y=eld.y-k*a/eld.d;             //求出当eld.x+k*（b/bel.d）=eld.y-k*（a/bel.d）的k值
            step1=cal(x,y);
            x+=b/eld.d;
            y-=a/eld.d;
            step2=cal(x,y);
        }
        printf("%lld\n",min(step1,step2));
    }
    return 0;
}