1631：【例 1】青蛙的约会

题目描述

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙 A 和青蛙 B ，并且规定纬度线上东经 $0$ 度处为原点，由东往西为正方向，单位长度 $1$ 米，这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 $x$ ，青蛙 B 的出发点坐标是 $y$ 。青蛙 A 一次能跳 $m$ 米，青蛙 B 一次能跳 $n$ 米，两只青蛙跳一次所花费的时间相同。纬度线总长 $L$ 米。现在要你求出它们跳了几次以后才会碰面。

输入格式

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

输出格式

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

样例

样例输入 #1

1 2 3 4 5

样例输出 #1

4

样例解释 #1

• 青蛙 A 起点 $x=1$，每次跳 $m=3$ 米；青蛙 B 起点 $y=2$，每次跳 $n=4$ 米；纬度线长 $L=5$ 米（环形）。
• 设跳了 $t$ 次后相遇，则青蛙 A 的位置为 $(x + m t) \bmod L$，青蛙 B 的位置为 $(y + n t) \bmod L$。
• 相遇条件：$(x + m t) \bmod L = (y + n t) \bmod L$，即 $x + m t \equiv y + n t \pmod{L}$。
• 整理得：$(m - n) t \equiv y - x \pmod{L}$。
• 代入数值：$(3-4) t \equiv 2-1 \pmod{5}$，即 $-t \equiv 1 \pmod{5}$，等价于 $t \equiv -1 \equiv 4 \pmod{5}$。
• 最小的正整数解 $t=4$。
• 输出 $4$。

数据范围

对于 $100\%$ 的数据：

• $0 \le x,y < 2 \times 10^9$
• $0 < m,n < 2 \times 10^9$
• $0 < L < 2 \times 10^9$
• 保证 $x \ne y$

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题是求解线性同余方程。设跳了 $t$ 次后相遇，则有：

移项得：

令 $a = m - n$，$b = y - x$，则方程化为：

这是一个线性同余方程，需要求最小正整数解 $t$。

解法：

1. 令 $d = \gcd(a, L)$。
2. 如果 $b$ 不能被 $d$ 整除，则无解，输出 Impossible。
3. 否则，方程两边同除以 $d$，得到：$$a' t \equiv b' \pmod{L'}$$ 其中 $a' = a/d$，$b' = b/d$，$L' = L/d$。
4. 此时 $\gcd(a', L') = 1$，可以用扩展欧几里得算法求 $a'$ 在模 $L'$ 下的逆元 $inv$，则 $t \equiv b' \cdot inv \pmod{L'}$。
5. 最小正整数解为 $t = (b' \cdot inv \bmod L' + L') \bmod L'$。
6. 注意 $t$ 可能为 $0$，但 $t=0$ 表示初始时刻相遇，但题目要求跳几次后相遇，且 $x \ne y$，所以 $t$ 应该大于 $0$。但 $t$ 可能是 $0$ 吗？当 $b' \cdot inv \equiv 0 \pmod{L'}$ 时 $t=0$，此时表示在初始时刻相遇，但 $x \ne y$ 不可能初始相遇，所以 $t=0$ 实际上对应 $t = L'$（即一个周期后）。因此最终解应为 $t = (b' \cdot inv \bmod L' + L') \bmod L'$，如果 $t=0$ 则 $t = L'$。

注意：$a = m - n$ 可能为负数，处理时将其转换为正数（模 $L$ 意义下）。$b = y - x$ 也可能为负数，同样处理。

计算过程中可能溢出，需要使用 long long。