### POJ 1061 解题报告：青蛙的约会
#### 问题描述
两只青蛙在互联网上相遇并决定在现实世界中相见。它们都位于同一纬度线上，因此计划各自向西跳跃直至碰面。然而，它们忘记了询问彼此的具体特征和会面地点。乐观的青蛙们相信只要持续朝着一个方向跳动，最终总会相遇。任务是编写一个程序来判断这两只青蛙是否能够碰面，以及何时能够碰面。
#### 输入格式
输入包含五个整数 x、y、m、n 和 L，分别表示青蛙 A 的起始位置坐标 x、青蛙 B 的起始位置坐标 y、青蛙 A 每次跳跃的距离 m、青蛙 B 每次跳跃的距离 n 和纬度线的总长度 L。其中 x ≠ y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
#### 输出格式
输出青蛙相遇所需的跳跃次数。若无法相遇，则输出 "Impossible"。
#### 解题思路
题目要求计算两只青蛙相遇所需的跳跃次数，关键在于分析青蛙们的跳跃模式及其与纬度线长度之间的关系。
- **问题转换**：首先将问题转换为数学表达式。假设青蛙 A 和青蛙 B 分别跳跃 t 步后相遇，则有以下等式成立：(x + mt) % L = (y + nt) % L。这里 % 表示取模运算，即求余数。
- **化简等式**：上述等式可以进一步化简为 (x - y) + (m - n)t = pL，其中 p 是某个整数。进一步整理得到 (m - n)t = (x - y) mod L。
- **模线性方程**：这个问题实质上转化为求解模线性方程 (m - n)t = (x - y) mod L 的最小正整数解 t 的问题。
- **求解方法**：求解模线性方程 ax = b (mod n) 的方法如下：
- 首先计算 a 和 n 的最大公约数 d = gcd(a, n)，并找到一组整数 x, y 使得 ax + ny = d。这一步可以通过扩展欧几里德算法完成。
- 如果 d 整除 b，则方程有解；否则无解。
- 若有解，可以进一步求得特解 x_0 = (x * (b / d)) mod n。之后所有通解可以表示为 x_i = x_0 + i * (n / d) mod n，其中 i 从 0 到 d - 1。
#### 算法实现
为了解决上述问题，需要实现以下功能：
- **扩展欧几里德算法**：用于计算 a 和 n 的最大公约数 d 以及满足 ax + ny = d 的整数 x 和 y 的值。
- **模线性方程求解器**：利用扩展欧几里德算法的结果求解模线性方程的最小正整数解。
#### 示例代码解析
以下是题目中的源代码的关键部分解析：
```cpp
#include<iostream>
using namespace std;
// 扩展欧几里德算法
__int64 ex_euclid(__int64 a, __int64 b, __int64& x, __int64& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
__int64 d = ex_euclid(b, a % b, x, y);
x = y;
y = x - a / b * y;
return d;
}
// 求解模线性方程
void modsolver(__int64 a, __int64 b, __int64 n) {
__int64 d, x0, y0;
d = ex_euclid(a, n, x0, y0);
if (b % d == 0) {
x0 = (x0 * (b / d)) % n;
x0 = (x0 + n) % n; // 确保结果为非负
cout << x0 << endl;
} else {
cout << "Impossible" << endl;
}
}
int main() {
int x, y, m, n, l;
cin >> x >> y >> m >> n >> l;
modsolver((n - m), (x - y), l);
return 0;
}
```
这段代码首先定义了一个扩展欧几里德算法 `ex_euclid` 来计算 a 和 n 的最大公约数 d 及其对应的系数 x 和 y。接着定义了模线性方程求解器 `modsolver`，用于解决给定的模线性方程问题。在主函数中读取输入并调用 `modsolver` 函数解决问题。
