题解 P2421 【[NOI2002]荒岛野人】

题目

luogu P2421

loj #10215

思路

设\(x\)相遇，显然\(x\in N_+\)

要求最小的正整数\(M\)，使得对于任意的\(i,j(1\leq i,j\leq n)\)同余方程\(c_i+p_i\times x \equiv c_j + p_i\times x(mod\ M)\)无解或\(x>min(l_i,l_j)\)（有其中一人死掉）

观察题目发现\(n\)很小，直接枚举即可

从小到大枚举\(M\)再枚举每一组\(i,j\)解同余方程判断即可

下面就剩下如何解同余方程的问题了

首先原式可变形为\(c_i + p_i\times x = c_j + p_i\times x + M\times y\)

然后化成丢番图方程的形式\((p_i-p_j)x+My = (c_j-c_i)\)

扩展欧几里得解方程就行

多说一句这道题的形式和扩展中国剩余定理有些相似

#include <bits/stdc++.h>
using namespace std;


const int N = 20;
int n,m = -1,c[N],p[N],l[N];


inline int read()
{
    register int x = 0;
    register char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9')
    {
        x = (x<<3)+(x<<1) + ch-'0';
        ch = getchar();
    }
    return x;
}


inline int exgcd(int a,int b,int &x,int &y)
{
    if(!a)
    {
        x = 0,y = 1;
        return b;
    }
    register int d = exgcd(b%a,a,y,x);
    x -= b / a * y;
    return d;
}

inline int gcd(int a,int b){return (!a?b:gcd(b%a,a));}

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


int main()
{
    n = read();
    for(register int i = 1;i <= n;i ++)
    {
        c[i] = read(); p[i] = read();l[i] = read();
        m = max(m,c[i]);
    }
    for(register int i = m;i;i ++)
    {
        if(check(i)) continue;
        cout << i << endl;
        break;
    }
    return 0;
}