Description

见 NOI 2018 屠龙勇士。

Analysis

Part I

首先我们注意到，对于每一条龙，击杀它所使用的剑是确定的。

根据题意，我们可以用权值线段树/平衡树/multiset 预处理出击杀第 $i$ 条龙所用的剑的攻击力，记为 $C_i$，$i=1,2\cdots,n$。

Part II

对于 $p_i=1$ 的这档部分分，显然只要龙的生命值非负就会死亡，故答案为 $\displaystyle\left\lceil\frac{A_i}{C_i}\right\rceil$ 的最大者。

Part III

观察数据范围我们可以发现，除去 $p_i=1$ 的测试点外，其余测试点满足 $a_i\le p_i$。

于是题意可转化为求方程组$$ \begin{cases} C_1x\equiv A_1\pmod{P_1}\\ C_2x\equiv A_2\pmod{P_2}\\ \cdots\cdots\cdots\cdots\cdots\cdots\\ C_nx\equiv A_n\pmod{P_n} \end{cases} $$ 的最小正整数解。

为了解决这个问题，我们首先将其转化为 exCRT 板子的标准形式$$ \begin{cases} x\equiv a_1\pmod{b_1}\\ x\equiv a_2\pmod{b_2}\\ \cdots\cdots\cdots\cdots\cdots\\ x\equiv a_n\pmod{b_n} \end{cases} $$ 如何转化呢？

考虑方程 $Cx\equiv A\pmod{P}$，可知存在整数 $y$ 使得 $Cx+Py=A$，用 exgcd 求解出它的一组特解 $x=x_0,y=y_0$。于是有 $x\equiv x_0\pmod{P/\gcd(C,P)}$，从而我们完成了上述转化。

exCRT 的部分直接 copy 模板即可，这道题好像就是板子题吧（

Code

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 1e5;
const int M = 1e5;
int T, n, m, len, tree[(N + N + M) << 2 | 1];
ll a[N + 1], b[N + 1], p[N + 1], force[M + 1], ATK[N + 1], C[N + 1];
ll ind[N + N + M + 1];

ll read()
{
    ll ans = 0; char ch;
    for(; !isdigit(ch = getchar()); );
    for(; isdigit(ch); ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar());
    return ans;
}
void build(int x, int l, int r)
{
    tree[x] = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
}
void update(int x, int l, int r, int p, int k)
{
    tree[x] += k;
    if(l == r) return;
    int mid = l + r >> 1;
    p <= mid ? update(x << 1, l, mid, p, k) : update(x << 1 | 1, mid + 1, r, p, k);
}
int query_pre(int x, int l, int r, int p)
{
    if(!tree[x]) return 0;
    if(l == r) return l;
    int mid = l + r >> 1;
    if(p <= mid) return query_pre(x << 1, l, mid, p);
    int ret = query_pre(x << 1 | 1, mid + 1, r, p);
    if(!ret) ret = query_pre(x << 1, l, mid, p);
    return ret;
}
int query_min(int x, int l, int r)
{
    if(l == r) return l;
    int mid = l + r >> 1;
    return tree[x << 1] ? query_min(x << 1, l, mid) : query_min(x << 1 | 1, mid + 1, r);
}
bool judge()
{
    for(int i = 1; i <= n; i++)
    {
        if(p[i] ^ 1)
            return 0;
    }
    return 1;
}
ll exgcd(ll &x, ll &y, ll a, ll b)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(x, y, b, a % b);
    ll k = y;
    y = x - (a / b) * y;
    x = k;
    return d;
}
ll mul(ll a, ll b, ll mod)
{
    ll ans = 0;
    for(; b; b >>= 1, a = (a + a) % mod)
        if(b & 1) ans = (ans + a) % mod;
    return ans;
}
int main()
{
    T = read();
    for(; T--; )
    {
        //a[i]: 第i条巨龙的初始生命值
        //p[i]：第i条巨龙的回血能力
        //ATK[i]：杀死第i条巨龙后获得的剑的攻击力
        //force[i]：第i把剑的攻击力 
        len = 0;
        n = read(), m = read();
        for(int i = 1; i <= n; i++)
            ind[++len] = a[i] = read();
        for(int i = 1; i <= n; i++)
            p[i] = read();
        for(int i = 1; i <= n; i++)
            ind[++len] = ATK[i] = read();
        for(int i = 1; i <= m; i++)
            ind[++len] = force[i] = read();
        sort(ind + 1, ind + len + 1);
        len = unique(ind + 1, ind + len + 1) - ind - 1;
        build(1, 1, len);
        for(int i = 1; i <= m; i++)
            update(1, 1, len, lower_bound(ind + 1, ind + len + 1, force[i]) - ind, 1);
        for(int i = 1; i <= n; i++)
        {
            int t = query_pre(1, 1, len, lower_bound(ind + 1, ind + len + 1, a[i]) - ind);
            if(!t) t = query_min(1, 1, len);
            C[i] = ind[t];
            update(1, 1, len, t, -1);
            update(1, 1, len, lower_bound(ind + 1, ind + len + 1, ATK[i]) - ind, 1);
        }
        if(judge())
        {
            ll ans = 0;
            for(int i = 1; i <= n; i++)
                ans = max(ans, (a[i] + C[i] - 1) / C[i]);
            printf("%lld\n", ans);
        }
        else
        {
            bool sol = 1;
            for(int i = 1; i <= n; i++)
            {
                ll x, y;
                ll d = exgcd(x, y, C[i], p[i]);
                if(a[i] % d)
                {
                    sol = 0;
                    break;
                }
//              printf("%dx = %d (mod %d) 等价于", C[i], a[i], p[i]);
                x = (x % p[i] + p[i]) % p[i];
                a[i] = mul(x, a[i] / d, b[i] = p[i] / d);
//              printf("x = %d (mod %d)\n", a[i], b[i]);
//              printf("%lld ", a[i]);
            }
//          break;
            if(!sol)
            {
                puts("-1");
                continue;
            }
            ll ans = a[1], m = b[1];
            for(int i = 2; i <= n; i++)
            {
                ll A = ((a[i] - ans) % b[i] + b[i]) % b[i];
                ll x, y;
                ll d = exgcd(x, y, m, b[i]);
                if(A % d)
                {
                    sol = 0;
                    break;
                }
                x = mul(x, A / d, b[i]);
                ans += m * x;
                m *= b[i] / d;
                ans = (ans + m) % m;
            }
            if(!sol) puts("-1");
            else printf("%lld\n", ans);
        }
    }
    return 0;
}