青蛙的约会

GitHub跳转原题关系图返回列表

跳 t 次后两蛙位置为 (x+mt) mod L 与 (y+nt) mod L，相遇条件化为同余方程 (m-n)t ≡ y-x (mod L)：gcd 判可达性，约简后用模逆元求最小非负解。

OJ: roj

题目 ID: 3099

难度:普及+/提高-

标签:数论扩展欧几里得同余方程python

创建: 2026-10-01 16:50

更新: 2026-10-07 13:50

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结
  4. 图示解析

形式化题目

给定整数 x,y,m,n,Lx, y, m, n, L。两只青蛙分别从环上位置 xx 与 yy 出发，每跳一次各自前进 mm 米与 nn 米，环长为 LL，即位置始终对 LL 取模。

求最小的非负整数 tt，使得两蛙第 tt 次跳跃后落在同一位置：

(x+mt) mod L=(y+nt) mod L;(x + m t) \bmod L = (y + n t) \bmod L;

若不存在这样的 tt，输出 Impossible。

数据范围：x≠y<2×109x \neq y < 2 \times 10^9，0<m,n<2×1090 < m, n < 2 \times 10^9，0<L<2.1×1090 < L < 2.1 \times 10^9。

样例 x=1, y=2, m=3, n=4, L=5x=1,\ y=2,\ m=3,\ n=4,\ L=5 的跳跃轨迹（位置对 55 取模）：

tt 0 1 2 3 4
青蛙 A (1+3t) mod 5(1+3t) \bmod 5 1 4 2 0 3
青蛙 B (2+4t) mod 5(2+4t) \bmod 5 2 1 0 4 3

第 4 次跳跃后两蛙同时落在位置 3，与样例输出 4 一致；表也显示出两条轨迹的周期都整除 LL，这正是后面把相遇写成同余方程的直观依据。

正解

思路

从模拟到同余方程。 最朴素的做法是模拟：每次跳跃后比较两蛙位置，直到相遇或确认循环。但位置序列的周期可以长达 L≈2.1×109L \approx 2.1 \times 10^9，模拟必然超时。注意到第 tt 次跳跃后两蛙的位置分别是 (x+mt) mod L(x + mt) \bmod L 与 (y+nt) mod L(y + nt) \bmod L，"同时落在同一点"就是

x+mt≡y+nt(modL),x + mt \equiv y + nt \pmod L,

移项得到一元线性同余方程

(m−n) t≡y−x(modL).(1)(m - n)\,t \equiv y - x \pmod L. \tag{1}

于是问题变成解同余方程 (1)，答案是它的最小非负整数解。

第一步：判断有没有解。 记 a=m−na = m-n，b=y−xb = y-x，g=gcd⁡(a,L)g = \gcd(a, L)（约定 gcd⁡(0,L)=L\gcd(0, L) = L）。左边 atat 模 LL 只能取到 gg 的倍数，由裴蜀定理，方程 (1) 有整数解当且仅当

g∣b.g \mid b.

若不整除，直接输出 Impossible。特别地，若 m=nm = n（即 a=0a=0），则 g=Lg = L；而 ∣y−x∣<L|y - x| < L 且 y≠xy \neq x，L∤bL \nmid b 必然无解——两个步长相同的青蛙永远追不上，判定自动覆盖，无需特判。

第二步：约简到系数可逆。 当 g∣bg \mid b 时，把 (1) 的系数、右端与模数同时除以 gg：

ag t≡bg(modM),M=Lg.(2)\frac{a}{g}\,t \equiv \frac{b}{g} \pmod{M},\qquad M = \frac{L}{g}. \tag{2}

此时 gcd⁡ ⁣(ag,M)=1\gcd\!\left(\frac{a}{g}, M\right) = 1，系数在模 MM 下可逆，且 (2) 与 (1) 同解。

第三步：取最小非负解。 两边乘上 ag\frac{a}{g} 的逆元：

t≡bg⋅(ag)−1(modM).t \equiv \frac{b}{g} \cdot \left(\frac{a}{g}\right)^{-1} \pmod M.

方程的全部整数解是 t0+kMt_0 + kM（t0t_0 为最小非负剩余）。跳跃次数必须非负，而 t0∈[0,M)t_0 \in [0, M) 已经是非负中最小的一个，所以 t0t_0 就是答案。

用样例验证：(1) 即 −t≡1(mod5)-t \equiv 1 \pmod 5，g=gcd⁡(−1,5)=1g = \gcd(-1, 5) = 1，逆元 (−1)−1≡−1(-1)^{-1} \equiv -1，故 t≡−1≡4(mod5)t \equiv -1 \equiv 4 \pmod 5，与轨迹表第 4 列吻合。

Python 实现中整条链路可以压成几个表达式：gcd(m - n, L) 给出 gg，b % g 做整除判定（Python 的 % 对负数返回非负余数，负系数无需特判），pow(a // g, -1, M) 用内建扩展欧几里得求模逆元，最后 % M 调进 [0,M)[0, M)。

代码

Python 版：

python
import sys
from math import gcd

def solve() -> None:
    """解 (m-n)*t ≡ (y-x) (mod L)：扩展欧几里得 + 最小非负解。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    x, y, m, n, L = next(data), next(data), next(data), next(data), next(data)
    a, b, mod = m - n, y - x, L           # a*t ≡ b (mod L)
    g = gcd(a, mod)                       # gcd 可能取到 0 当且仅当 a=0
    if b % g:                             # b 不是 g 的倍数 => 无解
        print("Impossible")
        return
    a, b, mod = a // g, b // g, mod // g  # 归一化：a*t ≡ b (mod mod)，gcd(a,mod)=1
    # a 的逆元 mod 意义下：pow(a, -1, mod)（Python 3.8+，内部扩展欧几里得）
    print(b * pow(a, -1, mod) % mod)

solve()

C++ 版（同一算法）：

cpp
/**
 * 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-06 18:42
 * update_at: 2026-10-06 18:42
 */

// 青蛙的约会：解同余方程 (m-n)*t ≡ (y-x) (mod L)，取最小非负解。
#include <cstdio>

typedef long long ll;

// 非负的辗转相除求 gcd。
ll gcd_ll(ll a, ll b) {
    if (a < 0) {
        a = -a;
    }
    if (b < 0) {
        b = -b;
    }
    while (b != 0) {
        ll t = a % b;
        a = b;
        b = t;
    }
    return a;
}

// 返回 nonnegative 的 a 在模 mod 下的逆元，调用前保证 gcd(a, mod) = 1。
ll mod_inverse(ll a, ll mod) {
    ll r0 = a, r1 = mod; // 辗转相除的两个余数
    ll s0 = 1, s1 = 0;   // 维护 a * s ≡ r (mod mod) 的系数
    while (r1 != 0) {
        ll q = r0 / r1;
        ll r2 = r0 - q * r1; // 先算新余数，再更新旧余数
        r0 = r1;
        r1 = r2;
        ll s2 = s0 - q * s1;
        s0 = s1;
        s1 = s2;
    }
    s0 %= mod;
    if (s0 < 0) {
        s0 += mod;
    }
    return s0;
}

int main() {
    ll x, y, m, n, L;
    if (scanf("%lld %lld %lld %lld %lld", &x, &y, &m, &n, &L) != 5) {
        return 0;
    }

    // 把相遇条件 x + m*t ≡ y + n*t (mod L) 移项成 a*t ≡ b (mod L)。
    ll a = m - n;
    ll b = y - x;
    ll g = gcd_ll(a, L); // gcd(0, L) = L，步长相同的情形自动判无解

    if (b % g != 0) { // 右边不是 g 的倍数，方程无整数解
        printf("Impossible\n");
        return 0;
    }

    // 约去公因子，此时 a/g 与 M 互质，系数可逆。
    ll mod = L / g;
    ll a_reduced = a / g;
    ll b_reduced = b / g;
    // 规约到 [0, mod) 内，方便后续求逆元和取答案。
    a_reduced %= mod;
    if (a_reduced < 0) {
        a_reduced += mod;
    }
    b_reduced %= mod;
    if (b_reduced < 0) {
        b_reduced += mod;
    }

    ll inv = mod_inverse(a_reduced, mod);
    ll answer = b_reduced * inv % mod; // 最小非负解即最少跳跃次数
    printf("%lld\n", answer);
    return 0;
}

复杂度

  • 时间复杂度：O(log⁡L)O(\log L)。一次 gcd 加一次模逆元，各为 O(log⁡L)O(\log L)，其余是 O(1)O(1) 算术。
  • 空间复杂度：O(1)O(1) 额外空间，与 LL 无关。

总结

题目把「环上两个等速点的追及」抽象成同余方程 (m−n)t≡y−x(modL)(m-n)t \equiv y-x \pmod L。gcd⁡(m−n,L)\gcd(m-n, L) 决定可达性，约去公因子后系数可逆，模逆元直接给出最小非负解。核心结论：答案只可能落在 [0, L/gcd⁡(m−n,L))[0,\ L/\gcd(m-n,L)) 内，模拟的 10910^9 量级周期被一次 O(log⁡L)O(\log L) 的数论运算取代；m=nm = n 的退化情形也被 gcd⁡(0,L)=L\gcd(0, L) = L 的约定自然覆盖。

图示解析

下图给出单组数据的判定与求解流程，重点看两条分支：无解分支在 gcd⁡\gcd 整除判定处直接结束；有解分支约去 gg 后，模 M=L/gM = L/g 的逆元运算一步给出答案。

flowchart TD
    Start[读入 x y m n L] --> G["g = gcd(m-n, L)"]
    G --> Div{g 整除 y - x ?}
    Div -- 否 --> Imp[输出 Impossible]
    Div -- 是 --> M["M = L / g"]
    M --> Inv["求 (m-n)/g 在模 M 下的逆元"]
    Inv --> Sol["t0 = (y-x)/g * inv mod M"]
    Sol --> Ans[输出 t0]

流程中唯一的"重"运算是模逆元，它对应 (2) 式两侧同乘逆元这一步。MM 既是约简后的模数也是解的周期，所以 t0t_0 一旦求出即是最少跳跃次数，无需回代验证。