又是一道扩欧的题。
要求一个最小的m使得 Ci+Pi*x≡Cj+Pj*x mod m(i!=j) 在x在第i个人和第j个人的有生之年无解。
也就是 (Pi-Pj)*x+m*y=Cj-Ci 在min(Li,Lj)上无解。
题目限制了保证有解且m<=1e6，那么可以考虑枚举m，在暴力地对每个人进行判断。
理论最差复杂度为1e6*n^2^log，但实际上远达不到这种情况。
需要注意的是m必须大于等于max(Ci)。
#include<complex>
#include<cstdio>
using namespace std;
const int N=;
int n;
int C[N],P[N],L[N];
int Exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=;y=;
return a;
}
int r=Exgcd(b,a%b,x,y),tmp=x;
x=y;y=tmp-a/b*y;
return r;
}
bool check(int m)
{
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
int x,y,a=abs(P[i]-P[j]),b=m,c=P[i]-P[j]>?C[j]-C[i]:C[i]-C[j];
int r=Exgcd(a,b,x,y);
if(c%r==)
if((x*(c/r)%(b/r)+(b/r))%(b/r)<=min(L[i],L[j]))
return ;
}
return ;
}
int main()
{
scanf("%d",&n);
int l=;
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&C[i],&P[i],&L[i]);
l=max(l,C[i]);
}
for(int i=l;i<=;i++)
if(check(i))
{
printf("%d\n",i);
break;
}
return ;
}