假设两只青蛙能碰面,且最少跳跃次数为t
则有式子$tm+x \equiv tn+y \pmod{L}$ 就是青蛙A和青蛙B经过k次跳跃的距离加上初始距离摸上L相等
式子又可以化为$tm+x+k_1L = tn+y+k_2L$
化简为$t(m-n)+(k_1-k_2)L=y-x$
其中m-n和L和y-x都为已知数,令$k_1-k_2$为k
那么式子就变成$at+bk=c$,用扩展欧几里得即可求解
因为通解$x=x_0+k*\frac{b}{d}$,d为(a,b)的最大公约数,所以答案需要对b/d取模,但是b/d可能是负数,所以需要取绝对值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x1,ll &y1)
{
if(b==0)
{
x1=1,y1=0;
return a;
}
ll d=exgcd(b,a%b,x1,y1);
ll t=x1;
x1=y1;
y1=t-a/b*y1;
return d;
}
int main()
{
ll x,y,m,n,l;
cin>>x>>y>>m>>n>>l;
ll a=m-n,b=l,c=y-x;
ll x1,y1;
ll d=exgcd(a,b,x1,y1);
if(c%d==0)
{
ll mod=abs(b/d);
x1=x1*(c/d);
ll ans=(x1%mod+mod)%(mod);
cout<<ans<<endl;
}
else puts("Impossible");
return 0;
}