Description
解题报告：
因为给定答案范围，暴力枚举时间，然后再两两枚举野人，判断是否有可能在某一年相遇，我们设这一年为(x),那么显然相交的条件是：
(x*(p[i]-p[j])+y*M=s[j]-s[i])
扩展欧几里得求得 (x) 的最小正整数解,判断这个线性方程的解是否存在且在他们寿命期内即可
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=20;
int n,s[N],p[N],lim[N];
ll exgcd(ll a,ll b,ll &x,ll &y){
if(a%b==0){x=0;y=1;return b;}
ll c=exgcd(b,a%b,x,y);
ll tmp=y;
y=x-a/b*y;
x=tmp;
return c;
}
bool judge(ll a,ll b,ll c,ll li){
ll x,y;
ll gcd=exgcd(a,b,x,y);
if(abs(c%gcd)!=0)return true;
x*=c/gcd;
ll d=b/gcd;if(d<0)d=-d;
x=((x%d)+d)%d;
if(x<=li)return false;
return true;
}
bool check(int x){
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(!judge(p[j]-p[i],x,s[i]-s[j],Min(lim[i],lim[j])))return false;
return true;
}
void work()
{
int mx=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&s[i],&p[i],&lim[i]),mx=Max(s[i],mx);
for(int i=mx;i<=1000000;i++){
if(check(i)){printf("%d
",i);return ;}
}
}
int main()
{
work();
return 0;
}