青蛙的约会

题意

两只青蛙分别从位置 x、y 出发，每次分别向前跳 m、n 米。
整条环形纬线总长是 L。

问它们最少跳多少次会落到同一个位置。
如果永远碰不到，输出 Impossible。

思路

先看一个最直接的小数据暴力：

cpp

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#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 x, y, m, n, L;
    cin >> x >> y >> m >> n >> L;

    // brute.cpp：小数据直接模拟跳跃过程。
    i64 cur_x = x;
    i64 cur_y = y;

    for (i64 step = 0; step <= L; step++) {
        if (cur_x == cur_y) {
            cout << step << '\n';
            return 0;
        }
        cur_x = (cur_x + m) % L;
        cur_y = (cur_y + n) % L;
    }

    cout << "Impossible\n";
    return 0;
}

暴力就是直接模拟每一次跳跃，看两只青蛙是否相遇。
这个思路最贴题意，但 L 很大，不能真模拟到天荒地老。

关键观察是：
如果它们在第 t 次跳跃后相遇，那么一定满足：

x + m t ≡ y + n t (mod L)

整理一下就是：

(m-n)t ≡ y-x (mod L)

这已经变成了标准的一次同余方程。

再把它写成整数方程：

(m-n)t + Lk = y-x

这正是扩展欧几里得处理的形式。

若设：

a = m-n
c = y-x

则方程：

a t ≡ c (mod L)

有解的充要条件是：

gcd(a, L) 能整除 c

如果不能整除，答案就是 Impossible。
如果能整除，就用 exgcd 求出一组解，再把 t 调整到最小非负值即可。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    i64 d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 x, y, m, n, L;
    cin >> x >> y >> m >> n >> L;

    i64 a = m - n;
    i64 c = y - x;

    if (a < 0) {
        a = -a;
        c = -c;
    }

    i64 p, q;
    i64 d = exgcd(a, L, p, q);

    if (c % d != 0) {
        cout << "Impossible\n";
        return 0;
    }

    i64 mod = L / d;
    i64 ans = (__int128) p * (c / d) % mod;
    ans = (ans % mod + mod) % mod;

    cout << ans << '\n';
    return 0;
}

复杂度

扩展欧几里得时间复杂度：

$O(log L)$

空间复杂度：

$O(1)$

总结

这题最核心的一步，就是把“第几次相遇”翻译成同余方程：

(m-n)t ≡ y-x (mod L)

一旦写出这个式子，后面就是一次同余方程模板题了。

目录

题意

思路

代码

复杂度

总结