记录编号	454202	评测结果	AAAAWAAAAA
题目名称	[NOI 2002]荒岛野人	最终得分	90
用户昵称	test	是否通过	未通过
代码语言	C++	运行时间	0.687 s
提交时间	2017-09-28 17:14:28	内存使用	0.31 MiB

//YPZ_YPZ_YPZ_YPZ_YPZ
#include<bits/stdc++.h>
#define ll long long
#define RG register
#define il inline
#define inf 707406378
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define file(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int N=16;
int C[N],P[N],L[N],M,n;

il int gi() {
    RG int res=0,f=1;RG char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}

int exgcd(int a,int b,int &x,int &y){
    if(!b){x=1;y=0;return a;}
    int z=exgcd(b,a%b,x,y),tmp;
    tmp=x;
    x=y;
    y=tmp-a/b*y;
    return z;
}

int main(){
    file("savage");
    n=gi(); rep(i,1,n) C[i]=gi(),P[i]=gi(),L[i]=gi();
    rep(i,1,n) if(C[i]==M) C[i]=0;
    int a,b,c,g;
    for(M=1;;M++){
	bool f=1;
	for(RG int i=1;i<n;i++) {
	    for(RG int j=i+1;j<=n;j++){
		int u=i,v=j;
		if(P[u]>P[v]) swap(u,v);
		a=P[u]-P[v],b=M,c=C[v]-C[u];
		a=(a%M+M)%M,c=(c%M+M)%M;
		int x,y;
		g=exgcd(a,b,x,y);
		if(c%g)continue;
		int k=c/g;
		x*=k,y*=k;
		int b2=b/g;
		x=(x%b2+b2)%b2;//　最小正整数解;
		if(x<=min(L[i],L[j])){f=0;break;}
	    }
	    if(!f)break;
	}
	if(f) {printf("%d",M);return 0;}
    }
    return 0;
}