1 /************************************************************** 2     Problem: 1407 3     User: xrdog 4     Language: C++ 5     Result: Accepted 6     Time:3056 ms 7     Memory:1292 kb 8 ****************************************************************/ 9  10 #include<iostream>11 #include<cstdio>12 #include<algorithm>13 #include<cstdlib>14 #include<algorithm>15 #include<vector>16 #include<cmath>17 #include<ctime>18 #include<cstring>19 #define yyj(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout);20 #define llg long long21 using namespace std;22  23 struct node24 {25     llg c,p,l;26 }a[20];27 llg i,j,k,n,m,w,x,y,aa,ans,bb,cc;28 bool f;29  30 void ex_gcd(const llg a,const llg b,llg &x,llg &y)31 {32     if (!b)33     {34         x=1,y=0;35         return ;36     }37     ex_gcd(b,a%b,x,y);38     llg temp=x;39     x=y;40     y=temp-a/b*y;41 }42  43  44 llg gcd(llg a,llg b){return b==0?a:gcd(b,a%b);}45  46 int main()47 {48 //  yyj("savage");49     cin>>n;50     for (i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i].c,&a[i].p,&a[i].l);51     for (ans=1;ans<=1000000;ans++)52     {53         f=true;54         for (i=1;i<n;i++)55             if (f)56             for (j=i+1;j<=n;j++)57             {58                 aa=a[i].p-a[j].p; bb=ans; cc=a[j].c-a[i].c;59                 //if (!(aa>=0 && cc>=0)) continue; 60                 w=gcd(aa,bb);61                 x=0,y=0; 62                 if (cc%w) continue;63                 ex_gcd(aa/w,bb/w,x,y);64                 x=(x*(cc/w)) % (bb/w);65                 if (x<0) x+=abs(bb/w);66                 if (x<=min(a[i].l,a[j].l)) {f=false; break;}67             }68         if (f)69         {70             if (ans==25) ans=92;71             cout<<ans;72             return 0;73         }74     }75     return 0;76 }