1. 题目

传送门=￣ω￣=

2. 题解

Emmmm… 我打同步赛的情况大概就是：看T1->哇可做赶紧写->写完了睡觉->醒来看知乎->哇还有30分钟下考没时间打暴力了->GG

还好不像 D1T1，这个还是 A 了的。。。

一开始看过去，可做啊大家怎么都不动手开始做。。。我也不敢做了啊。。。（后面发现可能是大家看到别人没动自己也不敢动）

好了讲正事。。。

首先那个什么拾起武器就是个逗比，每次用哪把武器攻击是固定的，拿个 multiset 预处理一下就行了。。。

现在考虑某只怪兽：

• 我们武器攻击力是 $k$
• 攻击 $x$次
• 怪物回血速度为 $p$
• 回血 $y$次
• 怪物血量为 $a$

那么：

$a-kx+py=0$且要满足 $a-kx\leq 0$

则：

$kx+py=a$（因为 $x,y$正负是随便的所以可以这样瞎 jb 变形）

很显然这就是个裸的扩展欧几里得（exgcd）。。。

假设搞出来的特解为 $x_0,y_0$（若无解则说明原问题无解输出-1 即可）

那么通解长这样：

• $x=x_0+q\frac{p}{gcd(p,k)}$
• $y=y_0-q\frac{k}{gcd(p,k)}$

其中 $q\in \mathbb {Z}$

而我们只要求 $x$的值，所以只要看第一个式子：$x=x_0+q\frac{p}{gcd(p,k)}$

这个式子可以理解为一个解集，我们把 $n$个解集取交然后找到最小解

可以想到用扩展 CRT：

把式子转化成同余方程：

$x\equiv x_0 \pmod{\frac{p}{gcd(p,k)}}$

这样我们就能获得一个 $n$个方程的童与方程组

用扩展中国剩余定理解之即可。

数据较大要用 long long+快速乘，为了卡常快速乘（代码中的 mul 函数）我用的 $O(1)$的，可以参考一下。

代码：

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

typedef long long LL;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

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

LL mul(LL a, LL b, LL M)
{
    a = a % M, b = b % M;
    return ((a * b - (LL)(((long double) a * b + 0.5) / M) * M) % M + M) % M;
}

int T, n, m;

namespace CRT
{
    LL a[NS], r[NS], mn;
    void work()
    {
        LL A = a[1], R = r[1], x, y, g, t;
        for (int i = 2; i <= n; i += 1)
        {
            g = exgcd(A, a[i], x, y);
            if ((r[i] - R) % g) puts("-1"), exit(0);
            t = a[i] / g, x = mul(x, (r[i] - R) / g % t + t, t), x = (x % t + t) % t;
            R = A * x + R, A = A / g * a[i], R %= A;
        }
        R = (R % A + A) % A;
        if (mn > R) R = R + A * ((mn - R) / A + ((mn - R) % A ? 1 : 0));
        printf("%lld\n", R);
    }
}

LL a[NS], p[NS], s[NS];

multiset<LL> st;

int main(int argc, char const* argv[])
{
    //freopen("dragon.in", "r", stdin), freopen("dragon.out", "w", stdout);
    IN(T);
    while (T--)
    {
        IN(n), IN(m), st.clear(), CRT::mn = LLONG_MIN;
        for (int i = 1; i <= n; i += 1) IN(a[i]);
        for (int i = 1; i <= n; i += 1) IN(p[i]);
        for (int i = 1; i <= n; i += 1) IN(s[i]);
        LL tmp, x, y, g; multiset<LL>::iterator it;
        for (int i = 1; i <= m; i += 1) IN(tmp), st.insert(tmp);
        for (int i = 1; i <= n; i += 1)
        {
            it = st.upper_bound(a[i]);
            if (it != st.begin()) it--, tmp = *it, st.erase(it);
            else tmp = *it, st.erase(it);
            CRT::mn = max(CRT::mn, a[i] / tmp + (a[i] % tmp ? 1 : 0));
            st.insert(s[i]), g = exgcd(tmp, p[i], x, y), x = (x % p[i] + p[i]) % p[i];
            if (a[i] % g) {puts("-1"); goto end;}
            a[i] /= g, p[i] /= g, CRT::a[i] = p[i], CRT::r[i] = mul(a[i], x, p[i]);
        }
        CRT::work();
        end : continue;
    }
    return 0;
}