洞穴数不超过1e6 ---> 枚举
判断每个野人两两之间是否发生冲突：exgcd
假设有$m$个洞穴，某两人（设为1,2）在$t$时刻发生冲突
那么我们可以列出方程
$c_{1}+p_{1}t\equiv c_{2}+p_{2}t (mod\quad m)$
移项一下：$(p_{1}-p_{2})t\equiv c_{2}-c_{1} (mod\quad m)$
去掉$(mod m)$，得$(p_{1}-p_{2})t-mx=c_{2}-c_{1} $
这不就是不定方程标准形式$ax+by=c$吗！
用exgcd搞搞，求出$t$的最小正整数解
如果$t<=min(l_{1},l_{2})$说明在两只的有生之年会发生冲突
此时$m$是不合法的，向下枚举就行了
复杂度$O(1e6n^{2}logp_{max})$，然鹅实际效率远高于介个
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
#define N 17
int n,C[N],p[N],l[N],x0,y0,g;
void exgcd(int a,int b,int &x,int &y){
if(!b) g=a,x=,y=;
else exgcd(b,a%b,y,x),y-=x*(a/b);
}
bool check(int b){
for(int i=,a,c,q;i<=n;++i)
for(int j=i+;j<=n;++j){
a=((p[i]-p[j])%b+b)%b,c=C[j]-C[i];
exgcd(a,b,x0,y0);q=b/g;//求ax+by=gcd(a,b)
if(c%g) continue;
x0=(x0*c/g%q+q)%q;//先*c/g转成原来的式子，再%(b/gcd(a,b))得到最小解
if(<=x0&&x0<=min(l[i],l[j]))
return ;
}
return ;
}
int main(){
scanf("%d",&n); int st=;
for(int i=;i<=n;++i)
scanf("%d%d%d",&C[i],&p[i],&l[i]),st=max(st,C[i]);
for(re int i=st;i<=;++i)//注意是从洞穴编号最大的那个开始枚举
if(check(i)){printf("%d",i);break;}
return ;
}