Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP4774 [NOI2018] 屠龙勇士

Posted on In
Symbols count in article: 1.9k Reading time ≈ 2 mins.

excrt ，难度在转化

屠龙勇士

思路

不难发现 $m_i$ 是确定的，可以预处理出来（用 multiset ），设其攻击力为 $atk_i$ ，那么则有 $atk_i * x \equiv a_i \pmod {p_i}$ 且 $atk_i * x \ge a_i$

仔细观察数据，发现特性 $1$ 导致 $atk_i * x \ge a_i$ 一定满足，去解前一个方程即可，考虑 exCRT ，去计算 $atk_i$ 在 $p_i$ 下的逆元，移项即化为一般形式；问题是 $atk_i$ 没有逆元的情况，此时不能直接认为无解，因为 $atk_i, a_i, p_i$ 可以同时约掉一个 $\gcd(atk_i, a_i, p_i)$ ，若不可约，才可以认为整个方程无解

而没有特性 $1$ 的点保证 $p_i == 1$ ，那么 $atk_i * x \equiv a_i \pmod {p_i}$ 一定满足，去解 $atk_i * x \ge a_i$ 即可

其实同时解两个方程其实也不是很麻烦，但观察数据的思想很好

代码

这里没有分讨数据，因为我懒

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using LL = long long;
using I128 = __int128;
using DB = double;
const int N = 1e5 + 100;
int n, m;
LL hp[N], p[N], sw[N], atk[N], dw, ans;
std::multiset<LL> s;
LL exgcd(LL a, LL b, LL &x, LL&y)
{
    if (!b){ return x = 1, y = 0, a; }
    LL d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}
LL excrt()
{
    LL x, y, k, P = p[1], res = hp[1];
    for (int i = 2; i <= n; ++i)
    {
        LL a = P, b = p[i], c = (hp[i] - res % b + b) % b;
        LL d = exgcd(a, b, x, y), bg = b / d;
        if (c % d != 0) return -1;
        x = I128(c / d) * x % bg;
        res += x * P;
        P *= bg;
        res = (res % P + P) % P;
    }
    res = (res % P + P) % P;
    while (res < dw) res += P;
    return res;
}
int main()
{
    int T;
    for (scanf("%d", &T); T--; )
    {
        scanf("%d %d", &n, &m), s.clear(), dw = 0;
        for (int i = 1; i <= n; ++i) scanf("%lld", hp + i);
        for (int i = 1; i <= n; ++i) scanf("%lld", p + i);
        for (int i = 1; i <= n; ++i) scanf("%lld", sw + i);
        while (m--)
        {
            LL t;
            scanf("%lld", &t);
            s.insert(t);
        }
        for (int i = 1; i <= n; ++i)
        {
            auto it = s.upper_bound(hp[i]);
            if (it != s.begin()) --it;
            atk[i] = *it;
            s.erase(it);
            s.insert(sw[i]);
        }
        for (int i = 1; i <= n; ++i)
        {
            LL x, y;
            LL d = exgcd(atk[i], p[i], x, y);
            if (hp[i] % d)
            {
                puts("-1");
                goto E_O_W_T;
            }
            hp[i] /= d, atk[i] /= d, p[i] /= d;
            exgcd(atk[i], p[i], x, y);
            x = (x % p[i] + p[i]) % p[i];
            dw = std::max(dw, (LL)std::ceil(DB(hp[i]) / atk[i]));
            hp[i] = I128(hp[i]) * x % p[i];
        }
        printf("%lld\n", excrt());
        E_O_W_T:;
    }
    return 0;
}