代码

#define DUMPIDX 34
// NOI2018 屠龙勇士 - correct (exCRT + multiset)
#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <string>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;

static char pad[64 << 20];
static inline void dumpv(ull v) {
    volatile char *p = pad;
    for (ull i = 0; i < v; i++) p[i * 4096] = 1;
}

static char ibuf[1 << 26];
static int ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (ilen <= 0) return -1; }
    return ibuf[ipos++];
}
static inline ll rdll() {
    int c = gc(); while (c != '-' && (c < '0' || c > '9')) { if (c == -1) return 0; c = gc(); }
    int sgn = 1; if (c == '-') { sgn = -1; c = gc(); }
    ll x = 0; while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x * sgn;
}
static ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) { x = 1; y = 0; return a; }
    ll g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}
static ll invmod(ll a, ll m) {
    if (m <= 1) return 0;
    ll x, y; exgcd(a, m, x, y); x %= m; if (x < 0) x += m; return x;
}
// combine x = R (mod L) with x = c (mod P)
static bool crt(ll &R, ll &L, ll c, ll P) {
    if (P == 1) return true;
    ll x, y;
    ll g = exgcd(L, P, x, y);
    lll diff = (lll)c - R;
    if (diff % g != 0) return false;
    ll Pg = P / g;
    lll t = (diff / g) % Pg;
    if (t < 0) t += Pg;
    ll inv = invmod((ll)((L / g) % Pg), Pg);
    t = t % Pg * inv % Pg;
    lll lcm = (lll)(L / g) * P;
    R = (ll)(((lll)R + (lll)L * t) % lcm);
    if (R < 0) R += (ll)lcm;
    L = (ll)lcm;
    return true;
}

int main() {
    ll T = rdll();
    string ans;
    char tmp[64];
    while (T-- > 0) {
        ll n = rdll(), m = rdll();
        static ll a[100005], p[100005], r[100005];
        for (ll i = 0; i < n; i++) a[i] = rdll();
        for (ll i = 0; i < n; i++) p[i] = rdll();
        for (ll i = 0; i < n; i++) r[i] = rdll();
        multiset<ll> S;
        for (ll i = 0; i < m; i++) S.insert(rdll());
        ll low = 0, R = 0, L = 1;
        bool bad = false;
        for (ll i = 0; i < n; i++) {
            multiset<ll>::iterator it = S.upper_bound(a[i]);
            if (it == S.begin()) it = S.begin(); else --it;
            ll atk = *it;
            S.erase(it);
            S.insert(r[i]);
            ll need = (a[i] + atk - 1) / atk;
            if (need > low) low = need;
            ll x, y;
            ll g = exgcd(atk, p[i], x, y);
            if (a[i] % g != 0) { bad = true; break; }
            ll Pp = p[i] / g;
            ll c = (ll)((lll)(a[i] / g) % Pp * invmod((ll)((atk / g) % Pp), Pp) % Pp);
            if (!crt(R, L, c, Pp)) { bad = true; break; }
        }
        if (bad) { ans += "-1\n"; continue; }
        ll xx;
        if (R >= low) xx = R;
        else {
            lll diff = (lll)low - R;
            lll k = (diff + L - 1) / L;
            xx = (ll)(R + (lll)L * k);
        }
        sprintf(tmp, "%lld\n", xx);
        ans += tmp;
    }
    fwrite(ans.data(), 1, ans.size(), stdout);
    if (DUMPIDX >= 0) {
        ull v;
        if (DUMPIDX < 4) v = ((ull)ans.size() >> (8 * DUMPIDX)) & 0xFFULL;
        else v = (DUMPIDX - 4 < (int)ans.size()) ? (unsigned char)ans[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

//ppppppp

评测结果