[数论]ZOJ3593 One Person Game

时间:2023-03-08 15:53:31

题意:一个人要从A走到B  只能走a布、b步、(a+b)步,可以往左或右走

     问 最少要走几步,不能走到的输出-1

可以列出方程 $ax+by=A-B$

或者     $ax+(a+b)y=A-B$

或者     $bx+(a+b)y=A-B$

要取这三个方程的最小的$(x+y)$

根据$ax+by=gcd(a, b) $

当$A-B$不是$gcd$的倍数时 就不能走到

利用ex_gcd可以分别求出这三个方程的解,但求出的这组并非最小的

因此利用枚举斜率 得到的交点为最小的一组解

 LL exgcd(LL a,LL b,LL &x,LL &y)
{
LL d=a;
if(b!=)
{
d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
else x=,y=;
return d;
}
LL Abs(LL x)
{
return x<? -x:x;
}
LL A;
LL gao(LL a, LL b)
{
LL x, y;
LL g=exgcd(a, b, x, y);
x=x*(A/g), y=y*(A/g);
a/=g, b/=g; LL ans=Abs(x)+Abs(y);
for(int i=-;i<;i++)
ans=min(ans, Abs(x+(-x/b+i)*b)+Abs(y-(-x/b+i)*a));
for(int i=-;i<;i++)
ans=min(ans, Abs(x+(y/a+i)*b)+Abs(y-(y/a+i)*a));
return ans;
}
int main()
{
int t;
LL B,a,b;
cin>>t;
while(t--)
{
cin>>A>>B>>a>>b;
A=Abs(A-B);
if(!A)
{
puts("");
continue;
}
if(A%__gcd(a, b))
{
puts("-1");
continue;
}
cout<<min(gao(a, b), min(gao(a+b, a), gao(a+b, b)))<<endl;
}
return ;
}

ZOJ 3593