形式化题目

环长为 $L$ 的圆周上有两个动点，初始位置 $x$、$y$（$x \neq y$），每一步分别前进 $m$、$n$。求最小的非负整数 $t$，使得

若这样的 $t$ 不存在，输出 Impossible。数据范围：$0 \leqslant x, y < 2 \times 10^9$，$0 < m, n, L < 2 \times 10^9$。

正解

思路

朴素做法与瓶颈。 最直接的想法是模拟：每一步让两只青蛙各前进一次，检查位置是否相同。单次跳跃后 A 领先 B 的距离减少 $m - n$（模 $L$ 意义下），所以相遇时间 $t$ 最大可能达到 $L$，而 $L < 2 \times 10^9$——模拟一步一查是 $O(L)$，必然超时。必须从"一步一跳"升级到"解方程"。

把相遇写成同余方程。 相遇条件是两者位置模 $L$ 相等：

移项，未知数只有 $t$：

这是一个标准的线性同余方程 $at \equiv c \pmod{L}$，其中 $a = m - n$，$c = y - x$。数据范围在 $2 \times 10^9$ 级别，Python 的整数不受影响，关键是求出 $t$ 的算法要降到 $O(\log L)$——这正是扩展欧几里得（exgcd）的用武之地。

用 exgcd 解同余方程。 设 $g = \gcd(a, L)$。由 Bézout 定理，exgcd 能求出整数 $s$ 使 $a \cdot s + L \cdot (\text{某整数}) = g$，即

• 有解判定：同余方程 $at \equiv c \pmod L$ 有解当且仅当 $g \mid c$。直观理解：$at - c$ 必须是 $L$ 的倍数，而 $g$ 同时整除 $a$ 与 $L$，所以 $g$ 必须整除 $c$。若 $g \nmid c$，输出 Impossible。
• 求特解：当 $g \mid c$ 时，把 Bézout 等式两边同乘 $c / g$，得特解 $t_0 = s \cdot \dfrac{c}{g}$，它满足 $a\,t_0 \equiv c \pmod L$。

从特解到最小非负解。 若 $t_0$ 是解，则 $t_0 + k \cdot \dfrac{L}{g}$ 也都是解（因为 $a \cdot \dfrac{L}{g}$ 恰好是 $L$ 的 $a/g$ 倍，模 $L$ 为 $0$）。所以全部解构成公差为 $\dfrac{L}{g}$ 的等差数列，最小非负解就是

实现的两个细节。 其一，$a = m - n$ 可能是负数（两只青蛙谁快谁慢不确定），Python 的 % 对负数返回非负余数，所以先做 $a \leftarrow (m-n) \bmod L$、$c \leftarrow (y-x) \bmod L$，把方程化成 $0 \leqslant a < L$、$0 \leqslant c < L$ 的标准形式，后续取模方向不会出错。其二，exgcd 递归返回的 $s$ 符号不定，最后一步统一 % step 归一化即可，无需手动调整符号。

用样例验证推导。 样例 $x=1, y=2, m=3, n=4, L=5$：方程为 $(-1)t \equiv 1 \pmod 5$，化成标准形 $a = 4,\ c = 1$，$g = \gcd(4,5) = 1$，特解 $s = 4$（$4 \times 4 = 16 \equiv 1$），周期 $L/g = 5$，答案 $4 \bmod 5 = 4$。逐跳模拟也能对上：第 $t$ 跳后 A 在 $(1+3t) \bmod 5$、B 在 $(2+4t) \bmod 5$，逐项列出：

观察重点：每一行 A 与 B 的差恰好减少 $1$（即 $m-n$ 的模 $L$ 效果），差值 $4, 3, 2, 1, 0$ 走完一个周期才追上——这正是方程 $4t \equiv 1 \pmod 5$ 的几何含义。当 $g > 1$ 时差值每次减少 $g$ 的倍数，差值永远落在 $g$ 的剩余类里，$g \nmid c$ 时就永远追不上，这解释了 Impossible 的来源。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 23:08
# update_at: 2026-09-30 23:08

import sys

IMPOSSIBLE = "Impossible"  # gcd(y-x, L) 不整除差值时的答案


def exgcd(a: int, b: int) -> tuple[int, int, int]:
    """返回 (g, s, t)，满足 a*s + b*t = g = gcd(a, b)，g 取非负。"""
    if b == 0:
        return a, 1, 0
    g, s, t = exgcd(b, a % b)
    return g, t, s - a // b * t  # 回代：a*x + b*y = g 的解由下层 (s,t) 推出


def solve() -> None:
    x, y, m, n, L = map(int, sys.stdin.buffer.read().split())

    # t 次跳跃后相遇 ⇔ x + m*t ≡ y + n*t (mod L) ⇔ (m-n)*t ≡ y-x (mod L)
    a = (m - n) % L            # 化成 0 ≤ a < L 的同余系数
    c = (y - x) % L            # 化成 0 ≤ c < L 的目标余数
    g, s, _ = exgcd(a, L)

    if c % g:
        print(IMPOSSIBLE)
    else:
        # a*s ≡ g (mod L)，两边乘 c/g 得特解，再除以 g/L 归一化周期
        step = L // g
        print(s * (c // g) % step)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:22
 * update_at: 2026-10-05 23:22
 */
// main.cpp：把相遇条件写成线性同余方程 (m-n)*t ≡ y-x (mod L)，用 exgcd 求最小非负解。

#include <cstdio>

typedef long long ll;

// 扩展欧几里得：返回 gcd(a, b)，并求出 x, y 使得 a*x + b*y = gcd(a, b)
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1; // 回代：下层解 (x1, y1) 推出本层解
    return g;
}

ll x, y, m, n, L; // 题目输入：起点、步长、环长

int main() {
    scanf("%lld %lld %lld %lld %lld", &x, &y, &m, &n, &L);

    // t 次跳跃后相遇 ⇔ x + m*t ≡ y + n*t (mod L) ⇔ (m-n)*t ≡ y-x (mod L)
    ll a = (m - n) % L; // 系数可能是负数，先归一化到 [0, L)
    if (a < 0) a += L;
    ll c = (y - x) % L; // 目标余数同样归一化到 [0, L)
    if (c < 0) c += L;

    ll s, k;
    ll g = exgcd(a, L, s, k); // a*s + L*k = g，即 a*s ≡ g (mod L)

    if (c % g != 0) { // g 不整除 c 时同余方程无解
        printf("Impossible\n");
        return 0;
    }

    // 两边同乘 c/g 得特解 t0 = s * (c/g)；全部解构成公差 L/g 的等差数列
    ll step = L / g;
    ll t = s % step * (c / g) % step; // 先取模防溢出，再归一化到最小非负解
    if (t < 0) t += step;
    printf("%lld\n", t);
    return 0;
}

代码要点与上文推导一一对应：

• exgcd 用递归实现 Bézout：边界 $b=0$ 时 $g=a,\ s=1$；回代时下层解 $(s, t)$ 变换为 $(t,\ s - a // b \times t)$。
• 主流程先把 $a$、$c$ 归一化到 $[0, L)$，再用 c % g 判无解；有解时特解 $s \cdot (c/g)$ 对周期 L // g 取模，直接得到最小非负解。

复杂度

• 时间复杂度：exgcd 的递归深度与辗转相除相同，为 $O(\log \min(a, L))$，其余步骤都是常数次大整数运算，总体 $O(\log L)$，远优于朴素模拟的 $O(L)$。
• 空间复杂度：递归栈 $O(\log L)$；改成迭代可以降到 $O(1)$，但递归写法与推导对应更直接。

总结

• 相遇条件 $\Leftrightarrow$ 线性同余方程 $(m-n)t \equiv y-x \pmod L$，是"循环追赶"类问题的标准转化。
• 解同余方程三步：exgcd 求 $g$ 与 Bézout 系数 → $g \mid c$ 判有解 → 特解乘 $c/g$ 后对周期 $L/g$ 取模得最小非负解。
• 负系数、大数取模是本题两个易错点：先 % L 化标准形，最后统一 % step 归一化，可以避免所有符号分类讨论。