考虑枚举山洞数量,问题变为判断一定数量的山洞是否合法。

设山洞数量为\(k\),即使得对于任意\(i,j\),满足

\(C_i+P_ix\equiv C_j+P_jx(mod\ k)\)

的最小正整数解(即两者相遇的最小天数)不存在或大于\(min(L_i,L_j)\)。

化简方程

\(C_i+P_ix\equiv C_j+P_jx(mod\ k)\)

\((P_i-P_j)x\equiv P_j-P_i(mod\ k)\)

\((P_i-P_j)x+ky\equiv P_j-P_i\)

扩展欧几里得求解即可。

(注:需要将\(P_i-P_j\)变为不影响答案的正整数,即\(((P_i-P_j)mod\ k+k)mod\ k\))

code:

#include
    
     using namespace std;int n,c[20],p[20],l[20],mnn,sv,mnv,tmp;int exgcd(int a,int b,int &solx,int &soly){//a*solx+b*soly=sv    if(!b){        if(sv%a)return 0;        solx=sv/a;        soly=0;        return a;    }    int sx,sy,t=exgcd(b,a%b,sx,sy);    if(t){        solx=sy;        soly=sx-(a/b)*sy;        return t;    }else return 0;}bool Solve(int d){    for(int i=1;i<=n;i++){        for(int j=i+1;j<=n;j++){            sv=c[j]-c[i];            int t=exgcd(((p[i]-p[j])%d+d)%d,d,mnv,tmp);            if(!t)continue;            int mod=d/t;            mnv=(mnv%mod+mod)%mod;            if(!mnv)mnv+=mod;            if(mnv<=min(l[i],l[j]))return false;        }    }    return true;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%d%d%d",&c[i],&p[i],&l[i]),mnn=max(mnn,c[i]);    for(int i=mnn;i<=1000000;i++)if(Solve(i))return printf("%d",i),0;    return 0;}