荒岛野人

OI 题解 数论 数学

算法：数论

转化成$\forall i, j,C_i+t*P_i\equiv C_j+t*P_j(\bmod m),t\le min(L_i,L_j)$

枚举$m$即可。

注意要从最大洞穴编号开始走。就这个我WA了3次。

代码

#include<cstdio>
#include<algorithm>
using std::swap;
using std::max;
typedef long long ll;
const int N = 15 + 5;
ll C[N], P[N], L[N];
ll n, m;
ll gcd(ll a, ll b) {
    return !b ? a : gcd(b, a%b);
}
void exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) {
        x = 1; y = 0;
    } else {
        exgcd(b, a%b, y, x);
        y -= (a/b)*x;
    }
}
inline bool check(ll x) {
    ll t, k, d;
    for (register int i = 1; i <= n; ++i) {
        for (register int j = i + 1; j <= n; ++j) {
            ll a = P[i] - P[j], b = x, c = C[j] - C[i];
            d = gcd(a, b);
            if (c % d) continue;
            a /= d, b /= d, c /= d;
            exgcd(a, b, t, k);
            if (b < 0) b = -b;
            t = (t*c%b + b) % b;
            if (!t) t += (x/d);
            if (t <= L[i] && t <= L[j]) return false;
        }
    }
    return true;
}
int main() {
    scanf("%d", &n);
    m = n;
    for (register int i = 1; i <= n; ++i) {
        scanf("%d %d %d", &C[i], &P[i], &L[i]);
        m = max(m, C[i]);//至少要满足编号要求
    }
    for (m; m <= 1000000; ++m) {
//      printf("%d\n", m);
        if (check(m)) {
            printf("%d\n", m);
            break;
        }
    }
    return 0;
}