首先根据题意,我们可以发现,两个野人 \(i, j\) 会处在一个山洞当且仅当存在 \(x\) 满足 \(C_i+xP_i\equiv C_j+xP_j \ (\bmod M)\) (\(M\) 为山顶数,\(x\) 为年数)当然,野人在 \(L_i\) 年后会死亡,故当最小正整数解 \(x > L_i\) 且 \(x > L_j\) 时,其实是不满足两个野人处在一个山洞的。那么本题要求的是没有两个野人会处在同一个山洞,即要找到最小的 \(M\) 满足对于任意的 \(i, j\),要么满足 \(C_i+xP_i\equiv C_j+xP_j \ (\bmod M)\) 无解,要么满足 \(C_i+xP_i\equiv C_j+xP_j \ (\bmod M)\) 的最小解 \(> \min\{L_i, L_j\}\)。
我们现在的问题就是解决 \(C_i+xP_i\equiv C_j+xP_j \ (\bmod M)\) 这个式子,我们考虑把式子变换一下,\(xP_i-xP_j\equiv C_j-C_i \ (\bmod M)\),\(x(P_i-P_j)\equiv C_j-C_i \ (\bmod M)\),\(x(P_i-P_j)+yM=C_j-C_i\)。
这个是非常经典的问题,我们考虑使用扩展欧几里得来解决。
不会可以看 我的博客。
题目说明了输入数据保证有解,且 \(M\) 不大于\(10^6\)。故我们考虑暴力枚举 \(M\) 然后 \(n^2\) 暴力枚举 \(i, j\) 判断是否成立。最后最坏复杂度:\(O(10^6\times n^2 \times \log(\max\{P_i, M\})\),但是考虑到根本卡不满,所以可以过。
还有一个小坑就是 \(M\) 一定 \(\geq max\{C_i\}\)。