青蛙的约会

题目描述

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。

它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。

坐标系统

我们把这两只青蛙分别叫做青蛙 A 和青蛙 B，并且规定：

• 纬度线上东经 0 度处为原点
• 由东往西为正方向
• 单位长度 1 米
• 这样就得到了一条首尾相接的数轴（即循环数轴，长度为 L）

初始条件

• 青蛙 A 的出发点坐标是 $x$
• 青蛙 B 的出发点坐标是 $y$
• 青蛙 A 一次能跳 $m$ 米
• 青蛙 B 一次能跳 $n$ 米
• 两只青蛙跳一次所花费的时间相同
• 纬度线总长 $L$ 米

问题

现在要你求出它们跳了几次以后才会碰面。

如果永远不可能碰面则输出一行 Impossible。

输入格式

输入只包括一行 5 个整数 $x, y, m, n, L$。

输出格式

输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行 Impossible。

数据范围

• $x \neq y < 2000000000$
• $0 < m, n < 2000000000$
• $0 < L < 2100000000$

输入样例

1 2 3 4 5

输出样例

4

样例解释

输入数据

• $x = 1$：青蛙 A 初始位置
• $y = 2$：青蛙 B 初始位置
• $m = 3$：青蛙 A 每次跳 3 米
• $n = 4$：青蛙 B 每次跳 4 米
• $L = 5$：纬度线总长 5 米

计算过程

设它们跳了 $t$ 次后相遇。

在循环数轴上，经过 $t$ 次跳跃：

• 青蛙 A 的位置：$(x + m \cdot t) \mod L$
• 青蛙 B 的位置：$(y + n \cdot t) \mod L$

它们相遇的条件是：

$$(x + m \cdot t) \equiv (y + n \cdot t) \pmod{L}$$

整理得：

$$(m - n) \cdot t \equiv (y - x) \pmod{L}$$

代入数值：

$$(3 - 4) \cdot t \equiv (2 - 1) \pmod{5}$$ $$(-1) \cdot t \equiv 1 \pmod{5}$$ $$t \equiv -1 \equiv 4 \pmod{5}$$

最小正整数解为 $t = 4$。

验证：

• 青蛙 A：位置 = $(1 + 3 \times 4) \mod 5 = 13 \mod 5 = 3$
• 青蛙 B：位置 = $(2 + 4 \times 4) \mod 5 = 18 \mod 5 = 3$
• 确实在位置 3 相遇

数学模型

相遇条件方程

设跳了 $t$ 次后相遇，则有：

$$x + m \cdot t \equiv y + n \cdot t \pmod{L}$$

移项得：

$$(m - n) \cdot t \equiv y - x \pmod{L}$$

转化为线性同余方程

令：

• $a = m - n$
• $b = y - x$
• 方程：$a \cdot t \equiv b \pmod{L}$

求解方法

这是一个线性同余方程，可以使用扩展欧几里得算法求解。

1. 方程等价于：$a \cdot t + L \cdot k = b$（$k$ 为整数）
2. 设 $d = \gcd(a, L)$
3. 如果 $d \nmid b$，则无解，输出 Impossible
4. 如果 $d \mid b$：
   • 将方程两边除以 $d$：$a' \cdot t + L' \cdot k = b'$，其中 $a' = a/d, L' = L/d, b' = b/d$
   • 用扩展欧几里得求 $a' \cdot t_0 + L' \cdot k_0 = 1$ 的解 $t_0$
   • 特解：$t = b' \cdot t_0$
   • 通解：$t = t + k \cdot L'$（$k$ 为整数）
   • 求最小正整数解：$t = (t \mod L' + L') \mod L'$

特殊情况

1. $m = n$ 的情况：

   • 如果 $x \neq y$，则永远追不上，输出 Impossible
   • 如果 $x = y$，则一开始就相遇，输出 $0$（但题目保证 $x \neq y$）

2. 位置差为 0 的情况：

   • 如果 $y - x \equiv 0 \pmod{L}$，它们一开始就在同一位置（模 L 意义下），输出 $0$

3. $a = m - n$ 可能为负数：

   • 需要处理负数情况，模运算中负数的处理要小心
   • 可以令 $a = ((m - n) \mod L + L) \mod L$ 化为正数

时空限制

• 时间限制：1秒
• 空间限制：10MB