这道题可谓是大毒瘤了，还要根据数据类型不同测试点不同的方法。
题目
题目描述
小 D 最近在网上发现了一款小游戏。游戏的规则如下：
- 游戏的目标是按照编号 (1 ightarrow n) 顺序杀掉 (n) 条巨龙，每条巨龙拥有一个初始的生命值 (a_i) 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 (p_i) ，直至生命值非负。只有在攻击结束后且当生命值 恰好 为 (0) 时它才会死去。
- 游戏开始时玩家拥有 (m) 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。
小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格，于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：
- 每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择 攻击力最低 的一把剑作为武器。
- 机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 (x) 次，使巨龙的生命值减少 (x imes ATK) 。
- 之后，巨龙会不断使用恢复能力，每次恢复 (p_i) 生命值。若在使用恢复能力前或某一次恢复后其生命值为 (0) ，则巨龙死亡，玩家通过本关。
那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数 (x) 设置为多少，才能用最少的攻击次数通关游戏吗？
当然如果无论设置成多少都无法通关游戏，输出 (-1) 即可。
输入格式
第一行一个整数 (T)，代表数据组数。
接下来 (T) 组数据，每组数据包含 (5) 行。
每组数据的第一行包含两个整数，(n) 和 (m) ，代表巨龙的数量和初始剑的数量；
接下来一行包含 (n) 个正整数，第 (i) 个数表示第 (i) 条巨龙的初始生命值 (a_i)；
接下来一行包含 (n) 个正整数，第 (i) 个数表示第 (i) 条巨龙的恢复能力 (p_i)；
接下来一行包含 (n) 个正整数，第 (i) 个数表示杀死第 (i) 条巨龙后奖励的剑的攻击力；
接下来一行包含 (m) 个正整数，表示初始拥有的 (m) 把剑的攻击力。
输出格式
一共 (T) 行。
第 (i) 行一个整数，表示对于第 (i) 组数据，能够使得机器人通关游戏的最小攻击次数 (x) ，如果答案不存在，输出 (-1)。
Solution
我刚开始看这道题时以为一把剑杀不死龙还可以再换一把继续杀，于是怎么也做不出，后来看看题解发现并不是这样。
是我自己没看清楚题，题目说：“每次面对巨龙时，玩家只能选择一把剑”。
然后思路就很清晰了，先预处理出杀死每一条龙要用的剑的攻击力，设其为 (ATK)，设第 (i) 条龙的生命值为 (h_i)。
题目的要求即为(h_i equiv ATKx(mod p_i))的最小正整数 (x)。
然而我们会发现一些问题：
如果(h_i le p_i)那这么写没问题，而如果(h_i > p_i)则有可能减不到负数就满足要求了。
而我们观察数据可得这种情况（即没有特殊性质1）时都是(p=1)，所以特判一下即可。
接着直接套excrt。
Q 如何转换为中国剩余定理的标准形式：(x equiv a (mod b))
A 通过exgcd解同余方程。
设当前同余方程为(axequiv b(mod m))，要变成标准形式。
先得到通解（如果得不到则无解）：(x=x0+kfrac{m}{gcd(a,m)}, k in Z)。
两遍同时mod(frac{m}{gcd(a,m)})得(x equiv x0 (mod frac{m}{gcd(a,m)}))
然后就可以愉快地套excrt了。
需要注意的一些东西：
-
如何求出每次用哪把剑——用一个multiset维护，每次找upperbound（注意这里剑的攻击力是可重的）。
-
如果(p_i | ATK)，则需满足(p_i | h_i)否则方程无解。而如果满足则这个方程算是一个废的方程，丢掉即可。
附上我调了一个下午的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
namespace IO{
template <typename T> void read(T &x) {
T f = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
x *= f;
}
template <typename T> void write(T x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void print(T x) {
if (x < 0) x = -x, putchar('-');
write(x);
putchar('
');
}
} using namespace IO;
int T;//测试组数
int n, m;//龙的数量、开始时剑的数量
ll h[N], p[N], a[N], b[N];//龙的血量、龙每次回复的血量、每次打完龙得到的剑的攻击力、开始m把剑的攻击力
ll ATK[N];//杀第i条龙用的剑的攻击力
multiset<ll> s;
ll nn, A[N], B[N];//excrt时方程的数量、值、模数
void init() {
s.clear();
for (int i = 1; i <= m; i++) s.insert(b[i]);//将剑放入set中
for (int i = 1; i <= n; i++) {
set<ll>::iterator it = s.upper_bound(h[i]);
if (it == s.begin()) ATK[i] = *it;
else ATK[i] = *--it;
s.erase(it);//注意这里是迭代器，否则会把所有值为ATK的都删掉
s.insert(a[i]);
}
}
void solve1() {
//如果全部p为1，则只需取 max{ceil(h[i]/ATK[i])} 即可
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, (ll)ceil(1.0 * h[i] / ATK[i]));
}
print(ans);
}
ll exgcd(ll u, ll v, ll &x, ll &y) {
if (v == 0) {
x = 1, y = 0;
return u;
}
ll g = exgcd(v, u % v, y, x);
y = y - u / v * x;
return g;
}
ll Mul(ll x, ll y, ll P) {
return (__int128)x * y % P;
}
bool init2() {
nn = 0;
for (int i = 1; i <= n; i++) {
if (ATK[i] % p[i] == 0 && h[i] % p[i] == 0) continue;
else if (ATK[i] % p[i] == 0 && h[i] % p[i] != 0) return false;
else {
ATK[i] %= p[i];
ll tmp, tmp2;
ll g = exgcd(ATK[i], p[i], tmp, tmp2);
if (h[i] % g) return false;
nn++;
B[nn] = (p[i] / g);
A[nn] = Mul(tmp, (h[i] / g), B[nn]);
A[nn] = (A[nn] % B[nn] + B[nn]) % B[nn];
}
}
return true;
}
ll solve2() {
//第二种情况，套excrt
if (!init2()) return -1;
ll X = A[1], M = B[1];
for (int i = 2; i <= nn; i++) {
ll z = (A[i] - X);
z = (z % B[i] + B[i]) % B[i];
ll t0, tmp;
ll g = exgcd(M, B[i], t0, tmp);
if (z % g) return -1;
t0 = Mul(t0, z / g, B[i] / g);
t0 = (t0 % (B[i] / g) + B[i] / g) % (B[i] / g);
X = X + M * t0;
M = M * (B[i] / g);
}
X = (X % M + M) % M;
return X;
}
int main() {
// freopen("dragon.in", "r", stdin);
// freopen("dragon.out", "w", stdout);
read(T);
while (T--) {
read(n); read(m);
for (int i = 1; i <= n; i++) read(h[i]);
for (int i = 1; i <= n; i++) read(p[i]);
for (int i = 1; i <= n; i++) read(a[i]);
for (int i = 1; i <= m; i++) read(b[i]);
init();
bool flag = 1;
for (int i = 1; i <= n; i++) if (p[i] != 1) {flag = 0; break;}//特判性质1，稍微压了压行
if (flag) {
solve1();
} else {
print(solve2());
}
}
return 0;
}