1637：荒岛野人

题目描述

克里特岛以野人群居而著称。岛上有排列成环行的 $M$ 个山洞。这些山洞顺时针编号为 $1,2,\cdots,M$。

岛上住着 $N$ 个野人，一开始依次住在山洞 $C_1,C_2,\cdots,C_N$ 中，以后每年，第 $i$ 个野人会沿顺时针向前走 $P_i$ 个洞住下来。每个野人 $i$ 有一个寿命值 $L_i$，即生存的年数。

奇怪的是，虽然野人有很多，但没有任何两个野人在有生之年处在同一个山洞中，使得小岛一直保持和平与宁静，这让科学家们很是惊奇。他们想知道，至少有多少个山洞，才能维持岛上的和平呢？

输入格式

第一行为一个整数 $N$，即野人的数目；

第二行到第 $N+1$ 每行为三个整数 $C_i, P_i, L_i$，表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。

输出格式

仅包含一个数 $M$，即最少可能的山洞数。输入数据保证有解，且 $M$ 不大于 $10^6$。

样例

样例输入 #1

3
1 3 4
2 7 3
3 2 1

样例输出 #1

6

样例解释 #1

• $N=3$ 个野人。
• 野人 1：初始山洞 $C_1=1$，每年走 $P_1=3$ 个洞，寿命 $L_1=4$ 年。
• 野人 2：初始 $C_2=2$，每年走 $P_2=7$ 个洞，寿命 $L_2=3$ 年。
• 野人 3：初始 $C_3=3$，每年走 $P_3=2$ 个洞，寿命 $L_3=1$ 年。
• 最少需要 $M=6$ 个山洞才能保证任何两个野人在有生之年不会相遇在同一山洞。
• 验证：当 $M=6$ 时，各野人的位置变化（模 $6$）：
  • 野人 1：第 $t$ 年位置 $(1 + 3t) \bmod 6$，$t=0,1,2,3$（寿命内）。
  • 野人 2：位置 $(2 + 7t) \bmod 6$，$t=0,1,2$。
  • 野人 3：位置 $(3 + 2t) \bmod 6$，$t=0$（只活一年）。
  • 检查所有 $t$ 组合，没有两个野人在同一年份处于同一山洞。
• 如果 $M$ 更小（如 $M=5$），则可能出现冲突。

数据范围

对于全部数据：

• $1 \le N \le 15$
• $1 \le C_i, P_i \le 100$
• $0 \le L_i \le 10^6$

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题需要找到一个最小的 $M$，使得对于任意两个野人 $i$ 和 $j$，在它们各自的有生之年（$0 \le t \le \min(L_i, L_j)$）内，不会出现同一年 $t$ 满足：

即

对每个野人对 $(i,j)$，我们需要确保该方程在 $t \in [0, \min(L_i, L_j)]$ 内无解（或者解不在该范围内）。

这是一个线性同余方程。设 $a = P_i - P_j$，$b = C_j - C_i$，方程 $a t \equiv b \pmod{M}$ 有解的条件是 $\gcd(a, M) \mid b$。如果有解，则解的形式为 $t \equiv t_0 \pmod{M/\gcd(a,M)}$。我们需要确保在 $[0, T]$（其中 $T = \min(L_i, L_j)$）内没有这样的 $t$。

由于 $N \le 15$，$M$ 不超过 $10^6$，我们可以枚举 $M$ 从 $\max(C_i)$ 开始（因为山洞数至少大于等于初始山洞编号的最大值），然后检查是否满足所有野人对都不冲突。检查时，对于每对 $(i,j)$，解方程 $a t \equiv b \pmod{M}$，判断是否存在 $t$ 在 $[0, T]$ 内满足。

具体检查方法： 对于给定的 $M$，对于每对 $i<j$：

1. 计算 $a = P_i - P_j$，$b = C_j - C_i$，$T = \min(L_i, L_j)$。
2. 方程化为 $a t \equiv b \pmod{M}$。
3. 令 $d = \gcd(a, M)$。
4. 如果 $b \bmod d \neq 0$，则方程无解，该对不会冲突。
5. 否则，方程有解。令 $a' = a/d$，$b' = b/d$，$M' = M/d$。
6. 求 $a'$ 在模 $M'$ 下的逆元 $inv$（因为 $\gcd(a', M')=1$），则特解 $t_0 = b' \cdot inv \bmod M'$。
7. 通解为 $t = t_0 + k M'$，$k$ 为整数。
8. 我们需要判断是否存在整数 $k$ 使得 $0 \le t \le T$。即 $t_0 + k M' \in [0, T]$。
9. 如果存在这样的 $k$，则冲突，$M$ 不满足条件；否则不冲突。

由于 $T$ 可能很大（$L_i$ 可达 $10^6$），但 $M'$ 不会超过 $M$，我们可以计算最小的非负解 $t_{\min} = t_0$，如果 $t_{\min} > T$ 则无冲突；否则检查 $t_{\min}$ 是否 $\le T$，如果是则冲突。但注意通解可能还有更小的解（因为 $t_0$ 是模 $M'$ 意义下的最小非负解，但可能大于 $T$，然而 $t_0 - M'$ 可能是负数，不考虑；或者 $t_0$ 本身在 $[0,T]$ 内）。所以只需要检查 $t_0$ 是否在 $[0,T]$ 内即可，因为如果 $t_0$ 不在范围内，那么其他解 $t_0 + k M'$ 要么更大（$k>0$），要么为负数（$k<0$），都不在 $[0,T]$ 内。因此，只需判断 $0 \le t_0 \le T$。

注意：当 $a=0$ 时，方程变为 $0 \cdot t \equiv b \pmod{M}$。如果 $b \equiv 0 \pmod{M}$，则对于所有 $t$ 都成立，即任意年份都冲突（除非 $T<0$ 但 $T\ge 0$），所以冲突；如果 $b \not\equiv 0 \pmod{M}$，则无解，不冲突。

算法步骤：

1. 读入 $N$ 和每个野人的 $C_i, P_i, L_i$。
2. 令 $M$ 从 $\max(C_i)$ 开始枚举到 $10^6$（因为保证有解且 $M \le 10^6$）。
3. 对于每个 $M$，检查所有野人对 $(i,j)$（$i<j$）是否冲突。
4. 如果所有对都不冲突，则输出 $M$ 并结束。

由于 $N \le 15$，野人对数最多 $105$，$M$ 最多 $10^6$，检查复杂度 $O(N^2 \log M)$，总计算量大约 $105 \times 10^6 \times \log M$ 可能太大（$10^8$ 级别），但实际 $M$ 不会枚举到 $10^6$ 那么多，因为答案可能较小。可以进一步优化：在检查时，如果发现冲突，立即跳出，枚举下一个 $M$。另外，由于 $M$ 是山洞数，必须是正整数，且至少为 $\max(C_i)$。

注意：野人的寿命 $L_i$ 可能为 $0$，表示该野人出生即死亡（当年就死），那么只需要检查 $t=0$ 时是否冲突。如果 $L_i=0$，则 $\min(L_i, L_j)=0$，只检查 $t=0$ 的情况，即初始位置是否相同。

实现时，注意取模运算可能产生负数，要调整到 $[0, M-1]$。