题解 P2421 【[NOI2002]荒岛野人】
ShineEternal
2019-10-02 08:03:10
[如有显示不完整请查看这里](https://blog.csdn.net/kkkksc03/article/details/101865848)
## description：
## solution：
观察到答案并不会很大，于是我们可以枚举答案（这里不满足单调性，不能二分）
对于任意的i,j，原式可变形 为$(Pi −Pj)*x −M *y = Cj −Ci$
于是这就是一个exgcd的模型
最后求出如果x不存在或者超过了野人的寿命m就是答案，否则就继续找。
## code:
```cpp
#include<cstdio>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int n;
int c[17],p[17],l[17];
int check(int m)
{
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int A=p[i]-p[j];
int B=m;
int C=c[j]-c[i];
int x,y;
int ans=exgcd(A,B,x,y);
if(C%ans)continue;
A/=ans;
B/=ans;
C/=ans;
if(B<0)B=-B;
x=(x*C%B+B)%B;
if(x<=l[i]&&x<=l[j])return 0;
}
}
return 1;
}
int max(int x,int y)
{
if(x>=y)return x;
return y;
}
int main()
{
scanf("%d",&n);
int start=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&c[i],&p[i],&l[i]);
start=max(start,c[i]);
}
for(int i=start;i;i++)
{
if(check(i))
{
printf("%d\n",i);
return 0;
}
}
}
```