Description

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

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

  • 游戏开始时玩家拥有 mm 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。

小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格， 于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：

  • 每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择攻击力最低的一把剑作为武器。
  • 机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 xx 次，使巨龙的生命值减少 x×ATKx \times ATK
  • 之后，巨龙会不断使用恢复能力，每次恢复 pip_i 生命值。若在使用恢复能力前或某一次恢复后其生命值为 00，则巨龙死亡，玩家通过本关。

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

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

Constraints

30pts:n,m≤105,pi=130pts: n,m\leq10^5 ,p_i=1

另外70pts:n,m≤105,ai≤pi,LCM(pi)≤101270pts: n,m\leq10^5, a_i\leq p_i, LCM(p_i)\leq10^{12}

Solution

考场上一开始还看错了题，以为一次打不死还可以换一把剑继续打。。。

首先，我们显然可以用multiset预处理出面对每条龙时用到的剑的攻击力(记为kik_i)

注意：

用set lower_bound时，必须用S.lower_bound(x)，而不能用lower_bound(S.begin(), S.end(), x)，否则会超时

并且multiset的删除必须要传迭代器，如果直接删除值的话会删除里面所有的这个数

题意可转化为求满足以下式子的xx的最小正整数解:

{k1x≡a1(mod p1) (a1−xk1≤0)k2x≡a2(mod p2) (a2−xk2≤0)...knx≡an(mod pn) (an−xkn≤0) \left\{ \begin{aligned} k_1x & \equiv a_1 (mod\ p_1) \ (a_1-xk_1\leq0) \\ k_2x & \equiv a_2 (mod\ p_2) \ (a_2-xk_2\leq0)\\ &...\\ k_nx & \equiv a_n (mod\ p_n) \ (a_n-xk_n\leq0) \end{aligned} \right.

  • 若pi=1p_i=1

    此时无论如何都能杀死所有龙，xx只需要满足ai−xki≤0a_i-xk_i\leq0那么答案即为max{⌈kiai⌉}\max\{\lceil \frac{k_i}{a_i}\rceil \}

  • 若ai≤pia_i\leq p_i

    此时xx只需要满足x≡ai∗ki−1(mod pi)x\equiv a_i * k_i^{-1} (mod\ p_i)

    我们用Ex_gcd不断合并方程组求解即可（具体见大佬的Blog）

    19.3.6 UPD 不用看大佬博客了，自己写了：求解模线性方程组 - ex_gcd

    几个需要注意的地方:

    1. 逆元有可能不存在，但是方程却有解。对于这种情况我们将方程全部同除undefined$即可

    2. 中间可能会爆long long，那么需要使用快速乘，快速乘中间一定要先对a和b取模，并且变成非负，再进行运算

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

const int maxn = 1e5 + 100;

int N, M;
int A[maxn], P[maxn], ATK[maxn], mod[maxn], rest[maxn]; 

inline int Plus (int &a, int b, int p) { a %= p; b %= p; (a += b) %= p; }

inline int Mult (int a, int b, int p)
{
	int ans = 0;
	a = (a % p + p) % p;
	b = (b % p + p) % p;
	while (b)
	{
		if (b & 1) Plus (ans, a, p);
		Plus (a, a, p);
		b >>= 1;
	}
	return ans;
}

inline void Exgcd (int a, int b, int &d, int &x, int &y)
{
	if (!b) d = a, x = 1, y = 0;
	else { Exgcd(b, a % b, d, y, x); y -= x * (a / b); }
}
inline int Inv (int a,int n)
{
	int d, x, y;
    Exgcd (a, n, d, x, y);
    return d == 1 ? (x + n) % n : -1;
}

inline int Solve()
{
	for (int i = 1; i < N; ++i)
	{
        int a = mod[i], b = mod[i + 1], c = rest[i + 1] - rest[i], gcd = __gcd(a, b), k1, k2, g;
        if (c % gcd) return -1;
        a /= gcd; b /= gcd; c /= gcd;
        Exgcd(a, b, g, k1, k2);
        k1 = (Mult(k1, c, b) + b) % b;
        mod[i + 1] = mod[i] / __gcd(mod[i], mod[i + 1]) * mod[i + 1] ;
        rest[i + 1] = (Mult(mod[i], k1, mod[i + 1]) + rest[i]) % mod[i + 1];
	}
    return rest[N];
}

multiset <int> S;

main()
{
	freopen("dragon.in", "r", stdin);
	freopen("dragon.out", "w", stdout);
	int T = read();
	while (T--)
	{
		S.clear();
		N = read(), M = read();
		for (int i = 1; i <= N; ++i) A[i] = read();
		int fl = 0;
		for (int i = 1; i <= N; ++i)
		{
			P[i] = read();
			if (P[i] != 1) fl = 1;
		}
		for (int i = 1; i <= N; ++i) ATK[i] = read();
		int ans = -1;
		for (int i = 1; i <= M; ++i) S.insert(read());
		for (int i = 1; i <= N; ++i)
		{
			multiset <int> :: iterator it = S.upper_bound(A[i]);
			if (it != S.begin())
				it--;
			rest[i] = *it;
			Chkmax(ans, (int)ceil((double)(1.0 * A[i] / rest[i])));
			S.erase(it);
			S.insert(ATK[i]);
		}
		if (!fl) cout<<ans<<endl;
		else
		{
			int flag = 0;
			for (int i = 1; i <= N; ++i)
			{
				mod[i] = P[i];
				int x = Inv(rest[i], mod[i]);
				if (x == -1) 
				{ 
					int g = __gcd(rest[i], mod[i]);
					int gg = __gcd(g, A[i]);
					if (gg != g)
					{
						flag = 1; break; 
					}
					else
					{
						rest[i] /= g, mod[i] /= g, A[i] /= g;
						x = Inv(rest[i], mod[i]);
					}
				}
				rest[i] = Mult(A[i], x, mod[i]);
			}
			if (flag) cout<<-1<<endl;
			else cout<<Solve()<<endl;
		}
	}
	return 0;
}