「Luogu P2421」「NOI2002」荒岛野人

Descripion

岛上有 $m$ 个洞穴，顺时针编号为 $1 \sim m$ 。岛上有 $n\ (1 \leq n \leq 15)$ 个野人分别住在 $c_1,c_2,\ldots,c_n\ (1 \leq c_i \leq 100)$ 中。以后每年，第 $i$ 个野人会沿顺时针向前走 $p_i\ (1 \leq p_i \leq 100)$ 个洞住下来，其中第 $i$ 个野人可以生存 $l_i$ 年。没有 $2$ 个野人能在有生之年生存在同一个洞穴中，求洞穴个数 $m\ (m \leq 10^6)$ 的最小值。

Source

[Luogu]P2421

Solution

前置知识：

扩展欧几里得(exgcd)算法

对于 野人 $i$ 和 野人 $j$ $(i \neq j)$，假设经过 $x$ 天之后他们会在同一个洞穴相遇，那么可以得出方程：

$$c_i + p_ix \equiv c_j + p_jx \pmod m$$

化简方程，得到

$$(p_i - p_j)x \equiv c_j - c_i \pmod m$$

这个方程等价于

$$(p_i - p_j)x + m \times y = c_j - c_i$$

显然我们可以用 exgcd(扩展欧几里得) 算法求出方程 $(p_i - p_j)x + m \times y = \gcd(p_i-p_j,m)$ 的一个解 $x’$ 。

如果 $\gcd(p_i-p_j,m) \nmid c_j-c_i$，说明 $x$ 无解，野人 $i,j$ 永远不会相遇。

若有解，我们求出 $x$ 的最小正整数解，即

$$x = \left( x' \times \frac{c_j - c_i}{\gcd(p_i-p_j,m)} \bmod \frac{m}{\gcd(p_i-p_j,m)} + \frac{m}{\gcd(p_i-p_j,m)} \right) \bmod \frac{m}{\gcd(p_i-p_j,m)}$$

如果 $x > \min(l_i,l_j)$，说明在他们相遇之前，$i, j$ 中会有至少一个野人死亡，所以也是可行的。

如果 $x \leq \min(l_i,l_j)$，说明 野人 $i,j$ 会在死亡前相遇，这个 $m$ 不可行。

我们只需要枚举每一个可能的 $m$（题目保证 $m \leq 10^6$），枚举每一对野人 $(i,j)$，用 exgcd 求解 $x$ 并判断这个 $m$ 是否满足要求。还有一些小细节：用 exgcd 时必须保证 $p_i \geq p_j$，因为 $\gcd$ 只对 非负整数 有意义。总时间复杂度为 $O( n^2m\log p_i)$ 。

Code

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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 15, MAXM = 1e6;
int n, maxn, c[MAXN + 5], p[MAXN + 5], l[MAXN + 5];

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

inline bool judge(int m) {//判断这个 m 是否可行
    for (int i = 1; i < n; ++i)
        for (int j = i + 1; j <= n; ++j) {//枚举每一对野人 
            int pi = p[i], pj = p[j], ci = c[i], cj = c[j], x, y, d;
            if (pi < pj) {
                swap(pi, pj);
                swap(ci, cj);
            } //如果 pi < pj，不满足 gcd 要求，交换 
            d = exGcd(pi - pj, m, x, y);//d = gcd(pi - pj, m)
            if ((cj - ci) % d != 0) continue;//x 无解，野人 i,j 不可能相遇 
            int p = m / d;
            x *= (cj - ci) / d;
            x = (x % p + p) % p;//x 的最小整数解 
            if (x <= min(l[i], l[j])) return 0;//这个 m 不符合题意 
        }
    return 1;
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        read(c[i]), read(p[i]), read(l[i]);
        maxn = max(maxn, c[i]);//已有洞穴中的编号最大的洞穴 
    }
    for (int i = maxn; i <= MAXM; ++i)//枚举洞穴个数，注意最小值为编号最大的洞穴 
        if (judge(i)) {
            write(i);
            putchar('\n');
            return 0;
        }
    return 0;
}