题意分析

题目背景

本题属于数论中的线性同余问题，模拟两只青蛙在环形轨道上跳跃的过程。给定它们的初始位置、每次跳跃的距离以及轨道长度，判断它们是否会相遇，并求出最早相遇时的跳跃次数。

核心问题

1. 相遇条件：
   设跳跃次数为$t$，需满足两只青蛙在$t$次跳跃后位于同一位置。

   • 青蛙A的位置：$(x + m \cdot t) \mod L$
   • 青蛙B的位置：$(y + n \cdot t) \mod L$
     等价于解方程：
   $$(x + m t) \equiv (y + n t) \pmod{L}$$

2. 方程转换：
   整理后得到标准线性同余方程：

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

   记为：

   $$a t \equiv b \pmod{L}$$

   其中$a = m - n$，$b = y - x$。

输入输出

• 输入：$x, y, m, n, L$（初始位置、跳跃距离、轨道长度）。
• 输出：最小正整数解$t$，或无解时输出Impossible。

---

解题思路

1. 线性同余方程的可解性

方程$a t \equiv b \pmod{L}$有解的条件是：

$$\gcd(a, L) \mid b$$

即$b$必须是$\gcd(a, L)$的倍数。

2. 扩展欧几里得算法

用于求解方程$a u + L v = \gcd(a, L)$的整数解$(u, v)$，进而得到特解$t_0$：

$$t_0 = u \cdot \frac{b}{\gcd(a, L)}$$

3. 通解与最小正整数解

通解形式为：

$$t = t_0 + k \cdot \frac{L}{\gcd(a, L)}$$

最小正整数解通过对$\frac{L}{\gcd(a, L)}$取模得到：

$$t_{\text{min}} = \left(t_0 \bmod \frac{L}{d} + \frac{L}{d}\right) \bmod \frac{L}{d} $$

其中$d = \gcd(a, L)$。

---

算法实现

代码框架

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    ll x, y, m, n, L;
    cin >> x >> y >> m >> n >> L;
    
    ll a = m - n;
    ll b = y - x;
    
    if (a < 0) {
        a = -a;
        b = -b;
    }
    
    ll t, k;
    ll d = exgcd(a, L, t, k);
    
    if (b % d != 0) {
        cout << "Impossible" << endl;
    } else {
        t = t * (b / d);
        ll mod = L / d;
        t = (t % mod + mod) % mod;
        cout << t << endl;
    }
    
    return 0;
}

关键步骤

1. 参数处理：
   确保$a = m - n$为正，同时调整$b = y - x$的符号。
2. 求解方程：
   调用exgcd解$a u + L v = d$，检查$b \bmod d$是否为0。
3. 计算解：
   特解缩放后取模得到最小正整数解。

---

复杂度分析

• 时间：$O(\log \min(a, L))$（扩展欧几里得算法）。
• 空间：$O(1)$。