MENU

洛谷P2421/BZOJ1407 [NOI2002]荒岛野人

洛谷P2421

BZOJ1407

枚举答案$ans$,exgcd判断是否合法。

$c_i+p_ix \equiv c_j+p_jx \pmod {ans}$无解或最小正整数解大于$\max(L_i,L_j)$

转化为$(p_i-p_j)x - ay \equiv c_j - c_i$

#include<cstdio>
#include<algorithm>
#if _WIN32||__WIN32__||_WIN64||__WIN64__||__CYGWIN__
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#if __unix__
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#if __GNUC__
#define inline __attribute__((always_inline))
#endif
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    template<class T = int>T rd() {
        int c = *iS++;
        T x = 0;
        for (; c < 48; c = *iS++);
        for (; c > 32; c = *iS++)x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(T x) {
        if (!x) { *oS++ = '0'; return; }
        int tp = 0;
        for (; x; st[++tp] = x % 10 + 48, x /= 10);
        for (; tp; *oS++ = st[tp--]);
    }
    io() :iS(ibuf), oS(obuf), oT(obuf + L - 1) { iT = iS + fread(ibuf, 1, L, stdin); }
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int N = ip.rd(), x, y, g, C[16], P[16], L[16], ans;
void exgcd(int a, int b){
    if (!b) { x = 1, y = 0, g = a; return; }
    exgcd(b, a%b);
    int t = x;
    x = y, y = t - a / b * y;
}
int main(){
    for (int i = 1; i <= N; ++i){
        C[i] = ip.rd(), P[i] = ip.rd(), L[i] = ip.rd();
        if (ans < C[i])ans = C[i];
    }
    for (;; ++ans){
        for (int i = 1; i < N; ++i)for (int j = i + 1; j <= N; ++j){
                int a = P[i] - P[j], c = C[j] - C[i];
                if (a < 0)a = -a, c = -c;
                exgcd(a, ans);
                if (c % g)continue;
                int mod = ans / g;
                if ((c / g * x % mod + mod) % mod <= std::min(L[i], L[j]))goto gg;
            }
        return ip.print(ans), 0;
    gg:;
    }
}
Leave a Comment

captcha
请输入验证码