bzoj 1407: [Noi2002]Savage

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\n",i);return ;}

   }

}

int main()

{

	work();

	return 0;

}