答案不大于 $10^6$，考虑枚举答案
对于枚举的 ans，必须满足对于任意 i,j(i≠j) 都有 使式子$c_i+kp_i equiv c_j+kp_j (mod ans)$成立的最小的 k ＞ min( L [ i ] , L [ j ] )
考虑如何求出式子中最小的 k
转化一下，变成$kp_i-kp_j+c_i-c_j=tcdot ans$
整理一下得 $k(p_i-p_j)-tcdot ans=c_i-c_j$
显然可以 exgcd 求 k
复杂度最高为 $O(MN^2log_M)$
但是实际上跑得飞快
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<iostream> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=27; int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0; return a;} int g=exgcd(b,a%b,x,y); int tmp=x; x=y; y=tmp-a/b*y; return g; } int n,c[N],p[N],L[N]; inline bool check(int M)//判断枚举的ans是否符合要求 { int X,Y,res,A,B,C,d,mo; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { A=p[i]-p[j],B=M,C=c[j]-c[i]; if(A<0) A=-A,C=-C;//负数要转正,B的符号对答案没影响 d=exgcd(A,B,X,Y); if(C%d) continue;//如果无解说明永远不会碰面，符合要求 res=X*C/d; mo=M/d; res=(res%mo+mo)%mo; if(res<=min(L[i],L[j])) return 0;//判断有生之年内是否会碰面 } return 1; } int main() { int mx=0; n=read(); for(int i=1;i<=n;i++) { c[i]=read(),p[i]=read(),L[i]=read(); mx=max(mx,c[i]); } for(int i=mx;i<=1e6;i++) if(check(i)) { printf("%d",i); break; } return 0; }