题目描述在一个神秘岛屿上有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,0001≤Ci,Pi≤1001 \leq C_i, P_i \leq 1001≤Ci​,Pi​≤1000≤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)(Cik⋅Pi) mod m pos_i(k) (C_i k \cdot P_i) \bmod mposi​(k)(Ci​k⋅Pi​)modm两个野人iii和jjj在第kkk天相遇的条件是(CikPi) mod m(CjkPj) 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)设APi−PjA P_i - P_jAPi​−Pj​BCj−CiB C_j - C_iBCj​−Ci​则上式变为kA≡B(modm) kA \equiv B \pmod{m}kA≡B(modm)我们需要确保在k0,1,…,min⁡(Li,Lj)k 0, 1, \dots, \min(L_i, L_j)k0,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)意义下唯一最小非负解可以通过扩展欧几里得算法求得算法思路枚举洞穴数从mmax⁡(Ci)m \max(C_i)mmax(Ci​)开始至少需要容纳所有野人的初始位置依次增加mmm直到找到满足条件的解检查条件对于每个候选mmm检查所有野人对(i,j)(i, j)(i,j)计算APi−PjA P_i - P_jAPi​−Pj​BCj−CiB C_j - C_iBCj​−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(log⁡m)O(\log m)O(logm)扩展欧几里得算法总复杂度O(t⋅106⋅n2log⁡m)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//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intn;intc[20],p[20],l[20];// 扩展欧几里得算法求解 ax by gcd(a,b)intexgcd(inta,intb,intx,inty){if(b0){x1;y0;returna;}intdexgcd(b,a%b,y,x);y-a/b*x;returnd;}// 检查m是否满足条件boolcheck(intm){for(inti0;in;i){for(intji1;jn;j){intAp[i]-p[j];intBc[j]-c[i];intmaxDaymin(l[i],l[j]);intd__gcd(A,m);if(B%d!0)continue;intnew_mm/d;intnew_AA/d;intnew_BB/d;// 处理负数情况if(new_A0){new_A-new_A;new_B-new_B;}new_B(new_B%new_mnew_m)%new_m;intx,y;exgcd(new_A,new_m,x,y);x(x%new_mnew_m)%new_m;intk0(longlong)x*new_B%new_m;if(k0maxDay)returnfalse;}}returntrue;}intmain(){intt;cint;while(t--){cinn;intmaxC0;for(inti0;in;i){cinc[i]p[i]l[i];maxCmax(maxC,c[i]);c[i]--;// 转换为0-based方便模运算}// 从maxC开始枚举mfor(intmmaxC;m1000000;m){if(check(m)){coutmendl;break;}}}return0;}总结本题的关键在于将野人相遇问题转化为同余方程求解问题通过数论方法判断在野人有生之年是否存在相遇的可能。算法采用枚举加验证的方式利用扩展欧几里得算法高效求解同余方程在题目数据范围内可以高效运行。