洞穴数不超过1e6 ---> 枚举
判断每个野人两两之间是否发生冲突：exgcd
假设有$m$个洞穴，某两人（设为1,2）在$t$时刻发生冲突
那么我们可以列出方程
$c_{1}+p_{1}tequiv c_{2}+p_{2}t (modquad m)$
移项一下：$(p_{1}-p_{2})tequiv c_{2}-c_{1} (modquad 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})$，然鹅实际效率远高于介个
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define re register 5 using namespace std; 6 int min(int a,int b){return a<b?a:b;} 7 int max(int a,int b){return a>b?a:b;} 8 #define N 17 9 int n,C[N],p[N],l[N],x0,y0,g; 10 void exgcd(int a,int b,int &x,int &y){ 11 if(!b) g=a,x=1,y=0; 12 else exgcd(b,a%b,y,x),y-=x*(a/b); 13 } 14 bool check(int b){ 15 for(int i=1,a,c,q;i<=n;++i) 16 for(int j=i+1;j<=n;++j){ 17 a=((p[i]-p[j])%b+b)%b,c=C[j]-C[i]; 18 exgcd(a,b,x0,y0);q=b/g;//求ax+by=gcd(a,b) 19 if(c%g) continue; 20 x0=(x0*c/g%q+q)%q;//先*c/g转成原来的式子，再%(b/gcd(a,b))得到最小解 21 if(0<=x0&&x0<=min(l[i],l[j])) 22 return 0; 23 } 24 return 1; 25 } 26 int main(){ 27 scanf("%d",&n); int st=0; 28 for(int i=1;i<=n;++i) 29 scanf("%d%d%d",&C[i],&p[i],&l[i]),st=max(st,C[i]); 30 for(re int i=st;i<=1000000;++i)//注意是从洞穴编号最大的那个开始枚举 31 if(check(i)){printf("%d",i);break;} 32 return 0; 33 }