题目大意是说,给一根长度为$L$的数轴,有两只青蛙分别从数轴的$x$和$y$位置开始向左跳,第一只青蛙的速度是$m$,第二只青蛙的速度是$n$,问这两只青蛙能否在相同时刻相同地点相遇
设两只青蛙在$t$时刻相遇,那么第一只青蛙的位置是$(mt+x)\ mod\ L$,第二只青蛙的位置是$(nt+y)\ mod\ L$,根据题目要求则要求方程$mt+x\equiv nt+y(mod\ L)$的解$t$
按照同余方程转化为裴蜀方程的证明步骤,我们这里也可以得到
$$ mt+x=Lk_1+p\\ nt+y=Lk_2+p $$
两式相减得$(m-n)t+(x-y)=L(k_1-k_2)$,移项$(m-n)t+Lk=y-x$
$x,y,m,n,L$都是已知的,直接带入线性方程求解即可得到$t$,如果求出的$t$小于0,还需要变换一下求出第一个大于0的解
import java.util.Scanner;
public class Main {
static long x, y;
static long exgcd(long a, long b) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long res = exgcd(b, a % b);
long x1 = x;
x = y;
y = x1 - (a / b) * y;
return res;
}
static long linearEquation(long a, long b, long m) throws Exception {
long d = exgcd(a, b);
if (m % d != 0)
throw new Exception("Impossible");
long n = m / d;
x *= n;
y *= n;
return d;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int a = cin.nextInt();
int b = cin.nextInt();
int m = cin.nextInt();
int n = cin.nextInt();
int l = cin.nextInt();
try {
long d = linearEquation(m-n, l, b-a);
l /= d;
l = l < 0 ? -l : l;
x = (x % l + l) % l;
System.out.println(x);
} catch (Exception e) {
System.out.println("Impossible");
}
}
}