[NOI2018]屠龙勇士

Posted on Edited on In Word count in article: 629 Reading time ≈ 2 mins.
excrt好题

[NOI2018]屠龙勇士

题目大意

你有一些刀，然后要去杀龙吃

没把刀都有自己的攻击力

然后固定每次砍它多少刀，然后龙还会回血。。。

如果能刚好回到零，这龙才是彻底的死了，可以吃了

否则输出 \(-1\)

Sulotion

对于这些剑​🗡​，你可以写平衡树维护，支持查询，删除，还有插入操作（还tm可能有重复元素）

算了，\(\text{STL}\)大法好，\(\text{multiset}\)全都支持的，理论上平板电视也可以（我离\(\text{AC}\)只差一个\(\text{C++11}\)）

那么假设已经得到了所有应该用的剑，那么就可以得到如下好东西： \[ \begin{cases} atk_2\cdot x\equiv a_1\pmod {p_1}\\ atk_2\cdot x\equiv a_2\pmod {p_2}\\ \quad\vdots\\ atk_3\cdot x\equiv a_3\pmod {p_3}\\ \end{cases}\\ \]

还要满足所有的\(atk_3\times x\ge p_3\)

所以还要维护一个\(\max(\left\lceil\frac {p_i}{atk_i}\right\rceil)\)

那么把所有的\(atk_i\)的逆元乘到右边去似乎就可以了？

由于题目并不保证互质，所以再操作前是一定一定要判断操作是否是可行的

似乎就结束啦

Code

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

ll a[maxn], p[maxn], b[maxn];
ll x, y, g;
multiset <ll> s;

void exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        g = a;
        return ;     
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

inline ll mul(ll a, ll b, ll mod)
{
    ll res = a * b - (ll)((ld)a / mod * b + 1e-8) * mod;
    return res < 0 ? res + mod : res % mod;
}

signed main()
{
    ll T = __read();
    multiset <ll> :: iterator it;
    __next: while (T--){
        ll n = __read(), m = __read();
        for (ll i = 1; i <= n; ++i) a[i] = __read();
        for (ll i = 1; i <= n; ++i) p[i] = __read();
        for (ll i = 1; i <= n; ++i) b[i] = __read();

        s.clear();

        for (ll i = 1; i <= m; ++i) s.insert(__read());

        ll mx(0), c(0);
        m = 1;

        for (ll i = 1; i <= n; ++i) {
            it = s.upper_bound(a[i]);
            if (it != s.begin()) --it;
            ll atk = *it;
            s.erase(it);
            s.insert(b[i]);
            mx = max(mx, (a[i] - 1) / atk + 1);
            atk %= p[i], a[i] %= p[i];
            if (!atk && a[i]) {
                puts("-1");
                goto __next;
            } else if (!atk && !a[i]) {
                continue;
            }
            
            exgcd(atk, p[i], x, y);
            if (a[i] % g) {
                puts("-1");
                goto __next;
            }

            p[i] /= g;
            a[i] = mul(a[i] / g, (x % p[i] + p[i]) % p[i], p[i]);

            exgcd(m, p[i], x, y);

            if ((a[i] - c) % g) {
                puts("-1");
                goto __next;
            }

            m = m / g * p[i];
            c = (c + mul(mul(m / p[i], (x % m + m) % m, m), ((a[i] - c) % m + m) % m, m)) % m;
        }

        printf ("%lld\n", c >= mx ? c : c + m * ((mx - c - 1) / m + 1));
    }
    system("pause");
}