BZOJ1407 [NOI2002]Savage

2015.02.22 15:29 Sun| 5 visits oi_2015| 2015_刷题日常| Text

Solution

回想起在 WC 和师大附中的帅哥一起熬夜好兴奋 >_< 哇咔咔咔。

观察到这道题中 M 的数据范围不大,于是枚举答案。如果对于任意一对野人 i, j,不存在 x 使得 $C_i + x * P_i = C_j + x * P_j\mod M$,若 x 的最小正整数解大于 $\min(L[i], L[j])$,当前的 M 符合题意。这样可以在 $\mathcal O(M\log M)$ 的时间内解决问题。

Code

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

int n, ans, c[16], p[16], l[16];

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

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

bool check(int m)
{
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
        {
            int x, y, g = exgcd(p[i] - p[j], m, x, y), t = abs(m / g);
            if ((c[j] - c[i]) % g) continue;
            x = ((x * (c[j] - c[i]) / g) % t + t) % t;
            if (x <= min(l[i], l[j])) return false;
        }
    return true;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        c[i] = read(), p[i] = read(), l[i] = read(),
        ans = max(ans, c[i] - 1);
    while (!check(++ans));
    cout << ans << endl;
}