题目描述
在一个神秘岛屿上，有nnn个疯狂的野人，他们生活在mmm个排成环形的洞穴中（编号111到mmm）。第iii个野人初始位于洞穴CiC_iCi，每天早晨他会顺时针移动到第PiP_iPi个洞穴，并且他只能存活LiL_iLi天。
野人喜欢打架，如果两个或更多野人在同一天出现在同一个洞穴，他们会战斗至死。但神奇的是，在题目条件下，所有野人在自然死亡前从未相遇过。
我们需要找出满足这一条件的最小洞穴数mmm。
数据范围：
- 测试用例数t≤10t \leq 10t≤10
- 野人数n≤15n \leq 15n≤15
- 洞穴数m≤1,000,000m \leq 1,000,000m≤1,000,000
- 1≤Ci,Pi≤1001 \leq C_i, P_i \leq 1001≤Ci,Pi≤100
- 0≤Li≤1,000,0000 \leq L_i \leq 1,000,0000≤Li≤1,000,000
题目分析
关键观察
对于野人iii，在第kkk天（0≤k≤Li0 \leq k \leq L_i0≤k≤Li）时，他所在的洞穴位置为：
posi(k)=(Ci+k⋅Pi) mod m pos_i(k) = (C_i + k \cdot P_i) \bmod mposi(k)=(Ci+k⋅Pi)modm
两个野人iii和jjj在第kkk天相遇的条件是：
(Ci+kPi) mod m=(Cj+kPj) mod m (C_i + kP_i) \bmod m = (C_j + kP_j) \bmod m(Ci+kPi)modm=(Cj+kPj)modm
这等价于：
(Ci−Cj)+k(Pi−Pj)≡0(modm) (C_i - C_j) + k(P_i - P_j) \equiv 0 \pmod{m}(Ci−Cj)+k(Pi−Pj)≡0(modm)
设A=Pi−PjA = P_i - P_jA=Pi−Pj，B=Cj−CiB = C_j - C_iB=Cj−Ci，则上式变为：
kA≡B(modm) kA \equiv B \pmod{m}kA≡B(modm)
我们需要确保在k=0,1,…,min(Li,Lj)k = 0, 1, \dots, \min(L_i, L_j)k=0,1,…,min(Li,Lj)范围内，该同余方程无解。
同余方程解的分析
对于方程kA≡B(modm)kA \equiv B \pmod{m}kA≡B(modm)：
- 有解条件：当且仅当gcd(A,m)∣B\gcd(A, m) \mid Bgcd(A,m)∣B
- 解的形式：如果解存在，则解在模m/gcd(A,m)m/\gcd(A, m)m/gcd(A,m)意义下唯一
- 最小非负解：可以通过扩展欧几里得算法求得
算法思路
- 枚举洞穴数：从m=max(Ci)m = \max(C_i)m=max(Ci)开始（至少需要容纳所有野人的初始位置），依次增加mmm直到找到满足条件的解
- 检查条件：对于每个候选mmm，检查所有野人对(i,j)(i, j)(i,j)：
- 计算A=Pi−PjA = P_i - P_jA=Pi−Pj，B=Cj−CiB = C_j - C_iB=Cj−Ci
- 如果gcd(A,m)∤B\gcd(A, m) \nmid Bgcd(A,m)∤B，则无解，继续检查下一对
- 否则，求最小非负解k0k_0k0
- 如果k0≤min(Li,Lj)k_0 \leq \min(L_i, L_j)k0≤min(Li,Lj)，则野人会在有生之年相遇，当前mmm不满足条件
- 输出结果：找到满足所有野人对都不相遇的最小mmm
复杂度分析
- 野人对数：O(n2)=O(152)=O(225)O(n^2) = O(15^2) = O(225)O(n2)=O(152)=O(225)
- 洞穴数枚举：最多1,000,0001,000,0001,000,000次
- 每次检查：O(logm)O(\log m)O(logm)（扩展欧几里得算法）
- 总复杂度：O(t⋅106⋅n2logm)O(t \cdot 10^6 \cdot n^2 \log m)O(t⋅106⋅n2logm)，在题目限制下可接受
代码实现
// Crazy Savages// UVa ID: 10413// Verdict: Accepted// Submission Date: 2025-11-15// UVa Run Time: 0.430s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intn;intc[20],p[20],l[20];// 扩展欧几里得算法，求解 ax + by = gcd(a,b)intexgcd(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returna;}intd=exgcd(b,a%b,y,x);y-=a/b*x;returnd;}// 检查m是否满足条件boolcheck(intm){for(inti=0;i<n;++i){for(intj=i+1;j<n;++j){intA=p[i]-p[j];intB=c[j]-c[i];intmaxDay=min(l[i],l[j]);intd=__gcd(A,m);if(B%d!=0)continue;intnew_m=m/d;intnew_A=A/d;intnew_B=B/d;// 处理负数情况if(new_A<0){new_A=-new_A;new_B=-new_B;}new_B=(new_B%new_m+new_m)%new_m;intx,y;exgcd(new_A,new_m,x,y);x=(x%new_m+new_m)%new_m;intk0=(longlong)x*new_B%new_m;if(k0<=maxDay)returnfalse;}}returntrue;}intmain(){intt;cin>>t;while(t--){cin>>n;intmaxC=0;for(inti=0;i<n;++i){cin>>c[i]>>p[i]>>l[i];maxC=max(maxC,c[i]);c[i]--;// 转换为0-based，方便模运算}// 从maxC开始枚举mfor(intm=maxC;m<=1000000;m++){if(check(m)){cout<<m<<endl;break;}}}return0;}总结
本题的关键在于将野人相遇问题转化为同余方程求解问题，通过数论方法判断在野人有生之年是否存在相遇的可能。算法采用枚举加验证的方式，利用扩展欧几里得算法高效求解同余方程，在题目数据范围内可以高效运行。
