题解：[NOI2002] 荒岛野人
分析
一、野人的相遇
记 $L$ 为洞穴数量。
两个野人相遇， 显然就是
$$
c_{1} + p_{1} x ≡ c_2 \ +p_2x (mod \ L)
$$
即
$$
c_1 + p_1x + L y=c_2+p_2x
$$
移项，合并同类项得
$$
(p_1 \ - p_2)x+Ly=c_2-c_1
$$
于是可以exgcd求解。
二、确定一个 $L$ 是否可行
由 $1≤N≤15$ 容易想到枚举野人。
$$
C{2}_{15}=\frac{A2_{15}}{A^2_2} =105
$$
$M≤10^6$， 每次枚举加判断的复杂度可以接受。
只要解出的 $x$ 小于两个野人的最小寿命， 那么这个 $L$ 不可行。
细节
- 在穷举答案的时候要从最大山洞编号开始穷举，否则会有错解。
- 一个 $L$ 被判为不可行后立即停止在当前 $L$ 下枚举野人，否则会超时。
- $a = b + kt$ ($b, \ t$ 为常数) 的最小非负整数值可以用 $((b \ mod \ t) + t) \ mod \ t $表示
代码
#include<bits/stdc++.h>
using namespace std;
#define show(x) cout << #x << " = " << x << "\n"
constexpr int N = 30, MAXN = 1000006;
int n, ans, x, y, MINN;
int c[N], p[N], l[N];
inline int gcd(int a, int b){if(!b)return a;return gcd(b, a % b);
}
inline void exgcd(int a, int b, int&x, int &y){if(!b){x = 1;y = 0;return;}exgcd(b, a % b, y, x);y -= a / b * x;
}
main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n;for (int i = 1; i <= n; i++){cin >> c[i] >> p[i] >> l[i];MINN = max(MINN, c[i]);}for (int L = MINN; L <= MAXN; L += 1){bool OK = 1;for (int i = 1; i < n && OK; i++){for (int j = i + 1; j <= n && OK; j++){int u = i, v = j;if (p[u] < p[v]) swap(u, v); int a = p[u] - p[v], b = L, D = c[v] - c[u];int Gcd = gcd(a, b);if (!Gcd || !a) continue;int k = D / Gcd;int LCM = a / Gcd * b;if ((D % Gcd) != 0) continue; //此组无解 => 不会相遇 exgcd(a, b, x, y);x *= k;int p = LCM / a;x = ((x % p) + p) % p;
// show(x);if (x <= min(l[i], l[j])) OK = 0;}}if (OK){cout << L << "\n";return 0;}}cout << "WRONG!!!!!\n";return 1;
}