洛谷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=
1;
y=
0;
}
else
{
exgcd(b,a%
b,x,y);
int t=
x;
x=
y;
y=t-a/b*
y;
}
}
bool check(
int ans)
{
for(
int i=
1;i<=n;i++
)
{
for(
int j=i+
1;j<=n;j++)
//枚举所有的野人
{
int a=P[i]-P[j],c=C[j]-C[i],b=ans,d=gcd(a,b),x=
0,y=
0;
if(c%d==
0)
//运用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=
1;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 0;
}
}
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9671291.html
