题目分类：数学，扩展gcd

题意：

给出n个野人的初始位置，速度和寿命，求出一个最小的环使得野人在有生之年不会相遇【野人神奇的活了1000000岁？】

题解：

枚举答案之后转化为求同余方程的最小自然数解，可以用扩展gcd解决。

程序：

#include<cstdio>
#include<algorithm>
using namespace std;
inline int extgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	int xx,yy,d=extgcd(b,a%b,xx,yy);
	x=yy;
	y=xx-a/b*yy;
	return d;
}
int n;
int c[20],p[20],l[20];
inline bool judge(int x,int y,int mm,int xx,int yy)
{
	int tx,ty;
	int td=extgcd(x,mm,tx,ty);
	if(y%td!=0)return false;
	tx*=y/td;
	while (tx>mm/td)tx-=mm/td;
	while (tx<0)tx+=mm/td;
	if(tx<=l[xx]&&tx<=l[yy])return true;
	return false;
}
inline bool check(int mm)
{
	for (int i=1;i<n;i++)
	{
		for (int j=i+1;j<=n;j++)
		{
			int tx=p[i]-p[j],ty=c[j]-c[i];
			if(tx<0)
			{
				tx=-tx;
				ty=-ty;
			}
			if(judge(tx,ty,mm,i,j))return true;
		}
	}return false;
}
int ans;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d %d %d",&c[i],&p[i],&l[i]);
		ans=max(ans,c[i]);
	}
	for (;check(ans);ans++);
	printf("%d\n",ans);
	return 0;
}