题目描述
小(D)最近在网上发现了一款小游戏。游戏的规则如下：游戏的目标是按照编号(1-n)顺序杀掉(n) 条巨龙，每条巨龙拥有一个初始的生命 值ai 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每 次增加 (p_i) ，直至生命值非负。只有在攻击结束后且当生命值恰好为 (0) 时它才会 死去。
游戏开始时玩家拥有(m)把攻击力已知的剑，每次面对巨龙时，玩家只能选择一 把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。 小(D) 觉得这款游戏十分无聊，但最快通关的玩家可以获得(ION2018) 的参赛资格， 于是小(D) 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：
每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择攻击力最低的一把剑作为武器。
机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的(x)次，使巨龙的生命值减少 (x imes ATK_x)
之后，巨龙会不断使用恢复能力，每次恢复pi 生命值。若在使用恢复能力前或 某一次恢复后其生命值为(0) ，则巨龙死亡，玩家通过本关。
那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小(D) 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数x 设置为多少，才能用最少的攻击次数通关游戏吗？
当然如果无论设置成多少都无法通关游戏，输出 (-1) 即可。
### 解题思路 :
观察发现，面对每一条龙时的攻击力 (atk_i) 是固定的，不妨用一个 (multiset) 求出.
考虑之后的部分，第 (i) 条龙要被打死当且仅当 ((a_i - x imes atk_i) | p_i) 且 (a_i leq x imes atk_i)
前一部分约束可以转化为 (x imes atk_i equiv ai ( mod p_i )) 可以直接用 (Exgcd) 求解出 (x)
注意：设 (g = gcd(atk_i, p_i)) 此时解出的 (x) 是在 ((mod frac{p_i}{g} )) 意义下成立的， 而不是 (p_i)
(ecause x imes atk_i equiv ai ( mod p_i ) ightarrow atk_ix + p_iy = a_i ightarrow atk_ifrac{x}{g} + p_ifrac{y}{g} = frac{a_i}{g})
用上述方法对于所有 ((atk_i, p_i)) 都能求出一个同余方程的解满足 (x equiv d_i (mod p'_i ))
因为要满足对于所有巨龙都要用同样的 (x) 杀死，所以需要用 (Excrt) 合并这些同余方程组
假设当前有两个方程组 $$ egin{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 imes atk_i)
可以把 (x) 代入到原有的数组里，判断是否满足限制，如果不满足就变成第一个比它大的解
注意：上述求类似 (ax + by = c) 的解的过程中，如果任意一步不满足 (gcd(a, b) | c) ，则整个方程组不可能有解，应该输出 (-1)
部分乘法过程中可能出现爆 (ll) 的情况，用快速乘来代替即可.
/*program by mangoyang*/
#include<bits/stdc++.h>
#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 <class T>
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<int> 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<int, int> 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<int, int> 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<int>::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<int, int> 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
", x);
}
main(){
int T; read(T); while(T--) solve();
return 0;
}