最近上课时提到的一道扩欧水题。还是很可做的。

我们首先注意到，如果一个数\(s\)是符合要求的，那么那些比它大（or 小）的数不一定符合要求。

因此说，答案没有单调性，因此不能二分。

然后题目中也提到\(s\le 10^6\)，因此我们直接从小到大枚举\(s\)，然后考虑如何判断。

由于两个野人在有生之年不会相遇，因此只有两种情况：

1. 这两个野人永远不会相遇。
2. 这两个野人相遇的时候他们其中的一个（或两个）已经死了。

在处理的时候我们把\(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;

}