形式化题目

给定 $N$ 个个体，每个个体 $i$（$1 \le i \le N$）具有三个属性 $(C_i, P_i, L_i)$，在模 $M$ 的环形空间上（编号 $1, 2, \dots, M$）按年份 $x \in [0, L_i]$ 运动，第 $x$ 年的位置为 $(C_i + x \cdot P_i - 1) \bmod M + 1$。

求最小的正整数 $M$，使得：

1. $M \ge \max_{1 \le i \le N} C_i$；
2. 对于任意两个个体 $i \neq j$，在整数区间 $x \in [0, \min(L_i, L_j)]$ 上，不存在整数 $x$ 使得：
   $$C_i + x \cdot P_i \equiv C_j + x \cdot P_j \pmod M$$

保证有解且 $M \le 10^6$。

正解：枚举山洞数 + 扩展欧几里得（exgcd）检验

思路

因为初始时每个野人分别住在不同的山洞中，山洞总数必须不小于所有初始位置的最大值，即 $M \ge \max_{1 \le i \le N} C_i$。

要求最小合法的 $M$，且保证 $M \le 10^6$，我们可以从 $M = \max C_i$ 开始依次递增枚举 $M$。对于每个 $M$，检验所有两两野人组合 $(i, j)$ 是否存在相遇冲突：

考虑野人 $i$ 与野人 $j$，设他们在第 $x$ 年位于同一山洞，则有：

移项整理为标准的线性同余方程：

记 $A = P_i - P_j$，$B = C_j - C_i$，$g = \gcd(A, M)$。根据裴蜀定理与同余方程性质：

1. 若 $B \bmod g \neq 0$，则方程无整数解，说明在该模数 $M$ 下，两野人永不相遇。
2. 若 $B \bmod g = 0$，由扩展欧几里得算法求出特解后，最小非负整数解为：
   $$x = \left( x_0 \cdot \frac{B}{g} \bmod \left|\frac{M}{g}\right| + \left|\frac{M}{g}\right| \right) \bmod \left|\frac{M}{g}\right|$$
   • 如果 $x \le \min(L_i, L_j)$，说明该最小非负解落在两人的共同寿命期内，发生了冲突，当前 $M$ 不合法，立即跳出尝试下一个 $M$。
   • 如果 $x > \min(L_i, L_j)$，由于后续解均满足 $x + k \cdot \left|\frac{M}{g}\right| \ge x > \min(L_i, L_j)$（$k \ge 0$），因此在两人的共同寿命期内绝无相遇可能。

只要存在任意一对野人相遇，当前 $M$ 就非法；若所有 $\binom{N}{2}$ 对野人均不相遇，则当前 $M$ 即为满足条件的最小山洞数。

冲突判定与相遇过程图示

以样例 $N=3$ 为例，当 $M=6$ 时各野人每年的轨迹如下表：

同余方程检验的判断流程可表示为：

flowchart TD
    Start[固定山洞数 M] --> LoopPair[枚举野人对 i, j]
    LoopPair --> Eq["方程 (P_i - P_j)x ≡ C_j - C_i (mod M)"]
    Eq --> Exgcd[调用扩展欧几里得求 gcd 与特解]
    Exgcd --> CheckDiv{B 是否被 gcd 整除?}
    CheckDiv -- 否 --> NoMeet[该对永远不相遇，继续下一对]
    CheckDiv -- 是 --> CalcMinX[计算最小非负整数解 x]
    CalcMinX --> CheckLife{x <= min(L_i, L_j)?}
    CheckLife -- 是 --> Collide[在有生之年相遇! M 非法]
    CheckLife -- 否 --> NoMeet
    Collide --> NextM[M 自增, 重新检验]
    NoMeet --> AllChecked{所有对均检验完毕?}
    AllChecked -- 否 --> LoopPair
    AllChecked -- 是 --> Success[找到最小合法 M, 输出并结束]

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72#!/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-04-18 10:00
# update_at: 2026-04-18 10:00

import sys
from itertools import combinations
from math import gcd

NO_COLLISION = True
COLLIDED = False


def extgcd(a: int, b: int) -> tuple[int, int, int]:
    """扩展欧几里得算法：返回 (g, x, y) 使得 a*x + b*y = g = gcd(a, b)。"""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extgcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def can_meet(
    c1: int, p1: int, l1: int, c2: int, p2: int, l2: int, m: int
) -> bool:
    """判断两个野人在给定山洞数 m 下，是否会在共同有生之年相遇。"""
    # 方程为：(p1 - p2) * x ≡ c2 - c1 (mod m)
    a = p1 - p2
    b = c2 - c1
    g, x, _ = extgcd(a, m)

    if b % g != 0:
        return False

    step = abs(m // g)
    x = (x * (b // g)) % step
    if x < 0:
        x += step

    limit = min(l1, l2)
    return x <= limit


def is_valid_m(
    savages: list[tuple[int, int, int]], m: int
) -> bool:
    """验证山洞总数为 m 时，所有野人之间是否均无冲突。"""
    for (c1, p1, l1), (c2, p2, l2) in combinations(savages, 2):
        if can_meet(c1, p1, l1, c2, p2, l2, m):
            return COLLIDED
    return NO_COLLISION


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)
    if n is None:
        return

    savages = [(next(data), next(data), next(data)) for _ in range(n)]
    m = max(c for c, _, _ in savages)

    while True:
        if is_valid_m(savages, m):
            print(m)
            return
        m += 1


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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89/**
 * 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:57
 * update_at: 2026-10-05 23:57
 */
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 20;

ll n;
ll C[MAXN], P[MAXN], L[MAXN]; // 第 i 个野人的初始山洞编号、每年前进洞数、寿命

// 扩展欧几里得：求 a*x + b*y = gcd(a,b)，返回最大公约数 g
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, x, y);
    ll tmp = y;
    y = x - (a / b) * y;
    x = tmp;
    return g;
}

// 判断野人 i 与野人 j 在 mod m 下是否会在共同寿命内相遇
// 相遇条件：(P_i - P_j) * x ≡ C_j - C_i (mod m)，x 为年数
bool can_meet(int i, int j, ll m) {
    ll a = P[i] - P[j];
    ll b = C[j] - C[i];
    ll x, y;
    ll g = exgcd(a, m, x, y);
    if (b % g != 0) {
        return false; // 无整数解，两人永不相遇
    }
    ll step = m / g;
    if (step < 0) {
        step = -step;
    }
    x = x * (b / g) % step; // 最小非负整数解
    if (x < 0) {
        x += step;
    }
    ll limit = min(L[i], L[j]);
    return x <= limit; // 解落在共同寿命内即冲突
}

// 检验山洞总数为 m 时，是否所有野人两两都不相遇
bool is_valid_m(ll m) {
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (can_meet(i, j, m)) {
                return false;
            }
        }
    }
    return true;
}

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

    cin >> n;
    ll start = 0; // 山洞数至少要不小于所有初始位置的最大值
    for (int i = 1; i <= n; i++) {
        cin >> C[i] >> P[i] >> L[i];
        if (C[i] > start) {
            start = C[i];
        }
    }

    // 保证有解且 M <= 10^6，从下界开始递增枚举
    for (ll m = start; ; m++) {
        if (is_valid_m(m)) {
            cout << m << "\n";
            break;
        }
    }

    return 0;
}

复杂度

• 时间复杂度：$O((M_{ans} - \max C_i) \cdot N^2 \log M)$。每次检验最多需检查 $\binom{N}{2} \le 105$ 对野人，单次扩展欧几里得为 $O(\log M)$。实际运行时由于剪枝效率极高，不合法的 $M$ 往往在前几对检验中就会被快速淘汰，能在时限内迅速找到解。
• 空间复杂度：$O(N)$，仅存储 $N$ 个野人的初始信息与常数变量开销。

总结

本题将环形追及相遇问题转化为模 $M$ 意义下的线性同余方程求解，通过扩展欧几里得算法快速求出最小非负整数解，判断解是否落在共同寿命区间内。结合 $N \le 15$ 的极小数据规模，外层直接递增枚举 $M$ 并配合极强的冲突早停剪枝即可高效求解。