最近上课时提到的一道扩欧水题。还是很可做的。
我们首先注意到，如果一个数\(s\)是符合要求的，那么那些比它大（or 小）的数不一定符合要求。
因此说，答案没有单调性，因此不能二分。
然后题目中也提到\(s\le 10^6\)，因此我们直接从小到大枚举\(s\)，然后考虑如何判断。
由于两个野人在有生之年不会相遇，因此只有两种情况：
- 这两个野人永远不会相遇。
- 这两个野人相遇的时候他们其中的一个（或两个）已经死了。
在处理的时候我们把\(c_i\)都减\(1\)方便处理。
我们接着枚举两个人\(i,j\)设它们\(x\)年后相遇，然后我们可以列出式子：
\(c_i+p_ix\equiv c_j+p_jx\ (mod\ s)\)
移项得
\((p_i-p_j)x-sy=c_j-c_i\)
然后就很明显了，我们扩欧解这个同余方程即可，再判断一下与\(min(l_i,l_j)\)的关系
但是注意一下枚举的下界，从\(min(c_i)\)（注意在减\(1\)之前计算）开始
CODE
#include<cstdio>
#include<cctype>
using namespace std;
const int N=20;
int n,c[N],p[N],l[N],mx;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
}
inline int min(int a,int b)
{
return a<b?a:b;
}
inline int exgcd(int a,int b,int &x,int &y)
{
if (!b) { x=1; y=0; return a; }
int d=exgcd(b,a%b,y,x); y-=a/b*x; return d;
}
inline bool check(int s)
{
register int i,j;
for (i=1;i<n;++i)
for (j=i+1;j<=n;++j)
{
int a=p[i]-p[j],b=s,k=c[j]-c[i],x,y;
if (a<0) a=-a,k=-k; int d=exgcd(a,b,x,y);
if (k%d) continue; x*=k/d; int r=b/d;
if ((x%r+r)%r<=min(l[i],l[j])) return 0;
}
return 1;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(n);
for (i=1;i<=n;++i)
read(c[i]),mx=c[i]>mx?c[i]:mx,--c[i],read(p[i]),read(l[i]);
for (i=mx;;++i)
if (check(i)) return printf("%d",i),0;
}