【NOI2002】荒岛野人

【题解】

可以枚举m

那么任意两个野人之间有 c[i]+x*p[i]=c[j]+x*p[j] (mod m)  无解，或 x 的最小值<=min(l[i] , l[j])

化为丢番图方程：(p[i]-p[j])*x+m*y=c[j]-c[i]

用扩展欧几里得搞就行了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<ctime>

 #include<algorithm>

 using namespace std;

 int n,mx,C[],p[],l[];

 inline int read()

 {

     int x=,f=;  char ch=getchar();

     while(!isdigit(ch))  {if(ch=='-')  f=-;  ch=getchar();}

     while(isdigit(ch))  {x=x*+ch-'';  ch=getchar();}

     return x*f;

 }

 int gcd(int a,int b)  {return b==?a:gcd(b,a%b);}

 void exgcd(int a,int b,int &x,int &y)

 {

     if(b==)  {x=;  y=;  return;}

     exgcd(b,a%b,x,y);

     int t=x;x=y;y=t-a/b*y;

 }

 bool check(int m)

 {

     for(int i=;i<=n;i++)

         for(int j=i+;j<=n;j++)

         {

             int a=p[i]-p[j],b=m,c=C[j]-C[i],x,y;

             int r=gcd(a,b);

             if(c%r==)

             {

                 a/=r;  b/=r;  c/=r;

                 exgcd(a,b,x,y);

                 b=abs(b);

                 x=((x*c)%b+b)%b;

                 while(!x)  x+=b;

                 if(x<=min(l[i],l[j]))  return ;

             }

         }

     return ;

 }

 int main()

 {

     //freopen("cin.in","r",stdin);

     //freopen("cout.out","w",stdout);

     n=read();

     for(int i=;i<=n;i++){C[i]=read();  p[i]=read();  l[i]=read();  mx=max(mx,C[i]);}

     for(int i=mx;;i++)  if(check(i))  {printf("%d\n",i);  break;}

     return ;

 }