代码

// P4774 [NOI2018] 屠龙勇士
// 500 MB 2000 ms

#include <bits/stdc++.h>

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define mst(a, k) memset(a, k, sizeof a)
#define minv(a, b) a = min(a, b)
#define maxv(a, b) a = max(a, b)

#define gcd(a, b) __gcd((ll)a, (ll)b)
#define lcm(a, b) (a / gcd(a, b) * b)
#define modv(a, p) ((a % p + p) % p)

#define gc(x) getchar(x)
#define pc(x) putchar(x)
#define put(x) printf("%d\n", x)
#define putl(x) printf("%lld\n", x)
#define mts() int t; scanf("%d", &t); while (t--) solve()

#define dbg(x...) fprintf(stderr, x)
#define dbgv(a, l, r) rep (i, l, r) fprintf(stderr, "%lld", (ll)a[i])

#define inf 0x3f3f3f3f
#define infl ((ll)1e18)

using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long;

template<int size = 1 << 20>
struct IO {
    char in[size], out[size], *p1, *p2, *pp;
    IO() : p1(in), p2(in), pp(out) {}
    ~IO() { fwrite(out, 1, pp - out, stdout); }
    inline char gc() { if (p1 == p2) p2 = (p1 = in) + fread(in, 1, size, stdin); return p1 == p2 ? ' ' : *p1++; }
    inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
    template<class T> inline void read(T& x) { double tmp = 1; bool sign = 0; x = 0; char ch = gc(); for (; !isdigit(ch); ch = gc()) sign |= ch == 45; for (; isdigit(ch); ch = gc()) x = x * 10 + ch - 48; if (ch == '.') for (ch = gc(); isdigit(ch); ch = gc()) tmp /= 10.0, x += tmp * (ch - '0'); if (sign) x = -x; }
    inline void read(char& c) { while (!blank(c)) c = gc(); }
    template<typename T, typename... Args> inline void read(T& x, Args&... args) { read(x), read(args...); }
    inline void push(const char& c) { if (pp - out == size) fwrite(out, 1, size, stdout), pp = out; *pp++ = c; }
    inline void write(char c) { push(c); }
    template<class T>
    inline void write(T x) { if (x < 0) x = -x, push('-'); static T sta[35]; T top = 0; do sta[top++] = x % 10, x /= 10; while (x); while (top) push(sta[--top] + '0'); }
    template<class T> inline void write(T x, char c) { write(x), push(c); }
    template<typename T, typename... Args> inline void write(const T x, const Args... args) { write(x), write(args...); }
};
IO<> io;

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

ll mul(ll a, ll b, ll p) {
    ll ans = 0;
    for (; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % p;
        a = (a + a) % p;
    }
    ans = (ans + p) % p;
    return ans;
}

constexpr int N = 1e5 + 7;

ll n, m, a[N], c[N], p[N], ap[N], atk[N];
multiset<ll> s;

ll excrt() {
    int f = 1;
    rep (i, 1, n) f &= p[i] == 1;
    if (f) {
        ll mx = 0;
        rep (i, 1, n) maxv(mx, (ll)ceil(1.0 * a[i] / atk[i]));
        return mx;
    } else {
        rep (i, 1, n) {
            ll x = 0, y = 0, res = exgcd(atk[i], p[i], x, y);
            x = 0, y = 0, res = exgcd(res, a[i], x, y);
            atk[i] /= res, p[i] /= res, a[i] /= res, x = 0, y = 0;
            ll g = exgcd(atk[i], p[i], x, y), G = p[i] / g;
            if (a[i] % g) return -1;
            else x = modv(x, G), c[i] = mul(x, a[i] / g, G);
        }
        
        ll ans = c[1], M = p[1], mx = 0;
        rep (i, 2, n) {
            ll res = modv(c[i] - ans, p[i]), x = 0, y = 0;
            ll g = exgcd(M, p[i], x, y), G = p[i] / g;
            if (res % g) return -1;
            x = mul(x, res / g, G), ans += x * M, M *= G;
            ans = modv(ans, M), maxv(mx, p[i]);
        }
        return modv(ans, M);
    }
}

void solve() {
    io.read(n, m);
    s.clear();
    
    rep (i, 1, n) io.read(a[i]);
    rep (i, 1, n) io.read(p[i]);
    rep (i, 1, n) io.read(ap[i]);
    rep (i, 1, m) { ll x; io.read(x), s.insert(x); } 
    
    rep (i, 1, n) {
        auto it = s.upper_bound(a[i]);
        if (it != s.begin()) --it;
        atk[i] = *it;
        s.erase(it), s.insert(ap[i]);
    }

    io.write(excrt(), '\n');
}

int main() {
    mts();
    
    return 0;
}

评测结果