题目描述

小\(D\)最近在网上发现了一款小游戏。游戏的规则如下：

游戏的目标是按照编号\(1-n\)顺序杀掉\(n\) 条巨龙，每条巨龙拥有一个初始的生命 值ai 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每 次增加 \(p_i\) ，直至生命值非负。只有在攻击结束后且当生命值恰好为 \(0\) 时它才会 死去。

游戏开始时玩家拥有\(m\)把攻击力已知的剑，每次面对巨龙时，玩家只能选择一 把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。 小\(D\) 觉得这款游戏十分无聊，但最快通关的玩家可以获得\(ION2018\) 的参赛资格， 于是小\(D\) 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：

每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择攻击力最低的一把剑作为武器。

机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的\(x\)次，使巨龙的生命值减少 \(x \times ATK_x\)

之后，巨龙会不断使用恢复能力，每次恢复pi 生命值。若在使用恢复能力前或 某一次恢复后其生命值为\(0\) ，则巨龙死亡，玩家通过本关。

那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小\(D\) 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数x 设置为多少，才能用最少的攻击次数通关游戏吗？

当然如果无论设置成多少都无法通关游戏，输出 \(-1\) 即可。

解题思路 :

观察发现，面对每一条龙时的攻击力 \(atk_i\) 是固定的，不妨用一个 \(multiset\) 求出.

考虑之后的部分，第 \(i\) 条龙要被打死当且仅当 \((a_i - x \times atk_i) \ |\ p_i\) 且 \(a_i \leq x \times atk_i\)

前一部分约束可以转化为 \(x \times atk_i \equiv ai \ ( \mod p_i\ )\) 可以直接用 \(Exgcd\) 求解出 \(x\)

注意：设 \(g = gcd(atk_i, \ p_i)\) 此时解出的 \(x\) 是在 \((\mod \frac{p_i}{g} \ )\) 意义下成立的， 而不是 \(p_i\)

\(\because x \times atk_i \equiv ai \ ( \mod p_i\ ) \rightarrow atk_ix \ + \ p_iy = a_i \rightarrow atk_i\frac{x}{g} + p_i\frac{y}{g} = \frac{a_i}{g}\)

用上述方法对于所有 \((atk_i, p_i)\) 都能求出一个同余方程的解满足 \(x \equiv d_i \ (\mod p'_i\ )\)

因为要满足对于所有巨龙都要用同样的 \(x\) 杀死，所以需要用 \(Excrt\) 合并这些同余方程组

假设当前有两个方程组 \[ \begin{cases} x \equiv a \ (\mod p_1g\ ) \\ x \equiv b \ (\mod p_2g \ ) \end{cases}\]

​ \(g = gcd(p_1g, \ p_2g)\)

设 \(x = a \ +\ k_1p_1g\) ，代入第二个方程得 $ a + k_1p1_g + k_2p_2g = b$

移项得 ：$k_1p_1+k_2p_2 = \frac{b-a}{g} $ 再次用 \(Exgcd\) 求解出 \(k1\) 即可得到 \(x\) 在 \((\mod \frac{p_1p_2}{g}\ )\) 的解了

合并出方程组的解后还需要满足第二个限制条件 \(a_i \leq x \times atk_i\)

可以把 \(x\) 代入到原有的数组里，判断是否满足限制，如果不满足就变成第一个比它大的解

注意：上述求类似 \(ax + by = c\) 的解的过程中，如果任意一步不满足 \(gcd(a, b) \ | \ c\) ，则整个方程组不可能有解，应该输出 \(-1\)

部分乘法过程中可能出现爆 \(ll\) 的情况，用快速乘来代替即可.

/*program by mangoyang*/#include
    
     #define inf (0x7f7f7f7f)#define Max(a, b) ((a) > (b) ? (a) : (b))#define Min(a, b) ((a) < (b) ? (a) : (b))typedef long long ll;using namespace std;template 
     
      inline void read(T &x){    int f = 0, ch = 0; x = 0;    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;    if(f) x = -x;}#define int ll#define fi first#define se second#define N (300005)multiset
      
        S;int a[N], b[N], c[N], p[N], atk[N], n, m;struct Node{ int x, m; } d[N];namespace Crt{    int Mod;    inline int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }    inline int Mult(int a, int b){        int ans = 0ll;        for(; b; b >>= 1, a = (a + a) % Mod)            if(b & 1) ans = (ans + a) % Mod;        return ans;    }       inline void exgcd(int a, int b, int &x, int &y){        if(!b) return (void) (x = 1ll, y = 0ll);        exgcd(b, a % b, y, x), y -= a / b * x;    }    inline pair
       
         get_exgcd(int a, int b, int c){        int g = gcd(a, b);        if(c % g) return make_pair(-1ll, -1ll);        int x, y; exgcd(a, b, x, y);        x = (x + Mod) % Mod, y = (y + Mod) % Mod;        x = Mult(x, c / g), y = Mult(y, c / g);        return make_pair(x, y);    }    inline Node merge(Node A, Node B){        if(A.x > B.x) swap(A, B);        int g = gcd(A.m, B.m); Mod = A.m / g * B.m;        pair
        
          now = get_exgcd(A.m, B.m, B.x - A.x);         if(now.fi == -1) return (Node){-1ll, -1ll};        return (Node){(A.x + Mult(A.m, now.fi)) % Mod, Mod};    }    inline Node solve(Node *A){        if(n == 1) return A[1];        Node now = merge(A[1], A[2]);        for(int i = 3; i <= n; now = merge(now, A[i]), i++)            if(now.x == -1 && now.m == -1) return now;        return now;    }}inline void init(){    read(n), read(m);    for(int i = 1; i <= n; i++) read(a[i]);    for(int i = 1; i <= n; i++) read(p[i]);    for(int i = 1; i <= n; i++) read(b[i]);    for(int i = 1; i <= m; i++) read(c[i]);}inline void prepare(){    S.clear();    multiset
         
          ::iterator q; for(int i = 1; i <= m; i++) S.insert(c[i]); for(int i = 1; i <= n; i++){ q = S.upper_bound(a[i]); if(q != S.begin()) q--; atk[i] = *(q), S.erase(q), S.insert(b[i]); }}inline void solve(){ init(), prepare(); for(int i = 1; i <= n; i++){ Crt::Mod = p[i]; pair
          
            now = Crt::get_exgcd(atk[i], p[i], a[i]); if(now.fi == -1) return (void) puts("-1"); d[i] = (Node){now.fi, p[i] / Crt::gcd(atk[i], p[i])}; } Node res = Crt::solve(d); if(res.x == -1 && res.m == -1) return (void) puts("-1"); int x = res.x, m = res.m; x %= m; for(int i = 1; i <= n; i++){ int ned = a[i] % atk[i] == 0 ? a[i] / atk[i] : a[i] / atk[i] + 1; if(x < ned){ int tmp = ned - x; if(tmp % m == 0) x += tmp / m; else x += tmp / m + 1; } } printf("%lld\n", x); }main(){ int T; read(T); while(T--) solve(); return 0;}