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