洛谷P2421：https://www.luogu.org/problemnew/show/P2421

思路

从洞的最大编号开始增大枚举答案

对于每一个枚举的ans要满足C_i+k*P_i≡C_j+k*P_j(mod ans)的k ,都要k>min(L[i],L[j]) 

因为这个ans一定要满足在一个野人死之前可以满足条件

根据上式可以推出C_i+k*P_i=C_j+k*P_j+m*ans   移项得k*(P_i-P_j)+m*ans=C_j-C_i

即可用Exgcd求解此式子

代码

#include
      
       #include
       
        #include
        
         using namespace std;#define maxn 20int 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<