洛谷2421 [NOI2002]荒岛野人

题意

有 $N$ 个野人，每个野人有初始所在的山洞 $C_i$、每次移动的山洞个数 $P_i$ 以及寿命 $L_i$ 。要求不存在有两个野人在同一年住在同一个洞穴，求山洞个数 $M$ 的最小值。

其中 $N\le 15$ ，保证 $M\le 10^{6}$ 。

题解

$N$ 比较小，所以可以枚举 $M$ （没有单调性没法二分），然后 $O(N^{2})$ 进行检验。

对每两个野人，题意可以化为要求下面的方程无解：

$$C_i+P_i\times x\equiv C_j+P_j\times x\pmod M \ , \ x>\min(L_i,L_j)$$

变形为

$$(P_i-P_j)\times x+M\times y=C_j-C_i$$

用 $\text{exgcd}$ 求解即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,m,C[20],p[20],l[20];

int exgcd(int l,int r,int &x,int &y)
{
    if (r==0)
    {
        x=1; y=0;
        return l;
    }
    int ans=exgcd(r,l%r,y,x);
    y-=l/r*x;
    return ans;
}

inline bool check(int m)
{
    for (int i=1;i<=n;i++)
    {
        for (int j=i+1;j<=n;j++)
        {
            int a=p[i]-p[j],b=m,c=C[j]-C[i],x=0,y=0;
            if (a<0) a=-a,c=-c;
            int g=exgcd(a,b,x,y);
            if (c%g) continue;
            b/=g; c/=g;
            x*=c;
            x=(x%b+b)%b;
            if (x<=l[i] && x<=l[j]) return 0;
        }
    }
    return 1;
}

int main()
{
    n=read();
    int mx=0;
    for (int i=1;i<=n;i++) C[i]=read(),p[i]=read(),l[i]=read(),mx=max(mx,C[i]);
    while (!check(mx)) mx++;
    return !printf("%d",mx);
}