洛谷P2421：https://www.luogu.org/problemnew/show/P2421
思路
从洞的最大编号开始增大枚举答案
对于每一个枚举的ans要满足Ci+k*Pi≡Cj+k*Pj(mod ans)的k ,都要k>min(L[i],L[j])
因为这个ans一定要满足在一个野人死之前可以满足条件
根据上式可以推出Ci+k*Pi=Cj+k*Pj+m*ans 移项得k*(Pi-Pj)+m*ans=Cj-Ci
即可用Exgcd求解此式子
代码
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define maxn 20
int n,Max;
int C[maxn],P[maxn],L[maxn];
int gcd(int a,int b)
{
if(!b) return a;
else
return gcd(b,a%b);
}
void exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=;
y=;
}
else
{
exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
}
}
bool check(int ans)
{
for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++)//枚举所有的野人
{
int a=P[i]-P[j],c=C[j]-C[i],b=ans,d=gcd(a,b),x=,y=;
if(c%d==)//运用Exgcd求解
{
a=a/d,b=b/d,c=c/d;
exgcd(a,b,x,y);
b=abs(b);
x=((x*c)%b+b)%b;
if(!x) x+=b;
if(x<=min(L[i],L[j])) return false;//满足一个野人已死亡
}
}
}
return true;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
cin>>C[i]>>P[i]>>L[i];
Max=max(Max,C[i]);//求出洞的最大编号
}
for(int i=Max;;i++)//ans至少要大于最大编号
{
if(check(i))//如果满足条件
{
cout<<i;
return ;
}
}
}