设跳的次数为t
根据题意可得以下公式：
(x+mt)%L=(y+nt)%L
变形得
(x+mt)-(y+nt)=kL
(n-m)t+kL=x-y
令a=(n-m),b=L,c=x-y
得 at+bk=c
此时就相当于求解二元不定方程ax+by=c的最小整数解
1、先计算Gcd(a,b)，若n不能被Gcd(a,b)整除，则方程无整数解；否则，在方程两边同时除以Gcd(a,b)，得到新的不定方程a' * x + b' * y = c'，此时Gcd(a',b')=1;
2、利用欧几里德算法求出方程a' * x + b' * y = （gcd）1的一组整数解x0,y0，则c' * x0,c ' * y0是方程a' * x + b' * y = c'的一组整数解；
3、根据数论中的相关定理，可得方程a' * x + b' * y = c'的所有整数解为：
x = c' * x0 + b' * t
y = c' * y0 - a' * t
(t为整数)
上面的解也就是a * x + b * y = c 的全部整数解。
此时方程的所有解为：x=c'*x0+b'*t,x的最小的可能值是0，令x=0可求出当x最小时的t的取值，但由于x=0是可能的最小取值，实际上可能x根本取不到0，那么由计算机的取整除法可知：由 t=-c'*x0/b'算出的t，代回x=c'*x0+b'*t中。
得minx=c'*x0+b'*[-c'*x0/b']
[]表示向下取整。
设A=c'*x0
可得 minx=A-A/b'*b'=A%b'=(c'*x0)%b'
#include<stdio.h> #include<string.h> typedef long long ll; ll ex_gcd(ll a,ll b,ll &x,ll &y){ if(!b){ x=1,y=0; return a; } ll ans=ex_gcd(b,a%b,y,x); y-=a/b*x; return ans; } ll cal(ll a,ll b,ll c){ ll x,y; ll d=ex_gcd(a,b,x,y); if(c%d) return -1; b/=d,c/=d; return ((x*c)%b+b)%b; } int main(){ ll x,y,v1,v2,l; while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&v1,&v2,&l)!=EOF){ ll ans=cal(v2-v1,l,x-y); if(ans==-1) printf("Impossible "); else printf("%I64d ",ans); } return 0; }