题目链接：
题目大意：这么长的题面，就饶了我吧emmm
这题第一眼看上去没法列出同余方程组。为什么？好像不知道用哪把剑杀哪条龙……
仔细一看，要按顺序杀龙，所以获得的剑出现的顺序也是固定的。
那么如果能把所有龙杀死，就能模拟出哪把剑杀那条龙了。
（以下设所有除 $n,m$ 外的数的最大值为 $v$）
$O(nm)$？
不，发现这里用剑的限制实际上是给出一个上界，来用lower_bound的。
插入也不要太暴力。我们想到什么？手写平衡树multiset！
这一部分复杂度是 $O(n\log m)$。
接下来就成了一个同余方程组：$atk_ix\equiv hp_i(\operatorname{mod}\ rec_i)$。
（$atk_i$ 表示攻击第 $i$ 条龙的攻击力，$hp_i$ 表示第 $i$ 条龙的血量，$rec_i$ 表示第 $i$ 条龙的恢复能力）
但是好像没那么简单！有一些神奇的情况……要特判！
在考场上的话我肯定想不到特判任何东西
首先大家应该都知道，$x\equiv a_i(\operatorname{mod}\ b_i)$ 等价于 $x\equiv a_i\ \operatorname{mod}\ b_i(\operatorname{mod}\ b_i)$。
但是在这题中不行！你总不能把一头龙的血量凭空减少吧！
所以 $hp_i>rec_i$ 时（题目描述中的特性1不满足时）怎么办？
我们发现不满足特性1的点都满足 $rec_i=1$……也就是只要把他的血量打到小于0就赢了！
此时答案是 $\max\limits_{1\le i\le n}(\lceil\frac{hp_i}{atk_i}\rceil)$。
另外要注意 $x\ge\max(\lceil\dfrac{hp_i}{atk_i}\rceil)$。
至此所有特判结束。
我们一般的EXCRT同余方程组的形式是 $x\equiv a_i(\operatorname{mod}\ b_i)$。
但是这里有讨厌的 $atk_i$！更讨厌的是可能没有逆元，不能直接除过去！
我们来看看如何变形：
$atk_ix\equiv hp_i(\operatorname{mod}\ rec_i)$
$atk_ix+rec_iy=hp_i$
此时可以EXGCD解出 $x$ 的最小正整数解 $x_0$。
根据某定理（什么定理来着？）可得通解为 $x=x_0+\frac{rec_i}{\gcd(atk_i,rec_i)}k(k\in N^+)$。
于是就变成了 $x\equiv x_0(\operatorname{mod}\ \frac{rec_i}{\gcd{atk_i},rec_i})$。
这一部分复杂度为 $O(n\log v)$。
接下来就是裸的EXCRT了！
这一部分复杂度为 $O(n\log v)$。
等一下，还有一句提示没看到：
你所用到的中间结果可能很大，注意保存中间结果的变量类型。
突然慌张
冷静分析一下，我们在各种算法中模数都有可能超过int范围，要是一乘……
那……只能上龟速乘了。时间复杂度是没变，但是常数的话……
幸好不是wys的题，不然时限就是1s了
好吧，都说完了，上代码吧。（之前因为数据水没有注意 $x\ge\max(\lceil\dfrac{hp_i}{atk_i}\rceil)$）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
multiset<ll> mts; //模拟拿剑
int t,n,m;
bool spec,exist,same;
ll hp[maxn],rec[maxn],a[maxn],b[maxn]; //a，b表示最后方程组是x=a_i(mod\ b_i)
int award[maxn],atk[maxn]; //award是奖励的剑
ll qmul(ll a,ll b,ll mod){ //*速乘
ll ans=;
for(;b;b>>=,a=(a+a)%mod) if(b&) ans=(ans+a)%mod;
return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y){ //模板
if(!b){x=;y=;return a;}
ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}
ll gcd(ll a,ll b){ //（不要问我为什么有这个）
if(!b) return a;
return gcd(b,a%b);
}
int main(){
scanf("%d",&t);
while(t--){
spec=false;same=exist=true; //spec是rec=1，same是hp=rec，exist是有没有解
mts.clear();
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%lld",hp+i);
for(int i=;i<=n;i++){scanf("%lld",rec+i);if(rec[i]<hp[i]) spec=true;} //rec<hp？
for(int i=;i<=n;i++) scanf("%d",award+i);
for(int i=;i<=m;i++){
int x;
scanf("%d",&x);
mts.insert(x); //全部进去
}
for(int i=;i<=n;i++){
multiset<ll>::iterator it;
if(hp[i]<*mts.begin()) it=mts.begin(); //如果没有比血量小的剑，则用第一把（最小的）
else it=mts.upper_bound(hp[i]),it--; //否则用第一个大于它的-1（即最后一个小于等于它的）
atk[i]=*it;
mts.erase(it);
mts.insert(award[i]); //拿走再选
}
if(spec){ //特判hp>rec
ll ans=;
for(int i=;i<=n;i++) ans=max(ans,ll(ceil(1.0*hp[i]/atk[i])));
printf("%lld\n",ans);
continue;
}
for(int i=;i<=n;i++){
if(!atk[i]){puts("-1");exist=false;break;} //无法攻击？无解
if(hp[i]!=rec[i]) same=false; //hp=rec?
ll x,y,d=exgcd(atk[i],rec[i],x,y); //解x0
if(hp[i]%d){puts("-1");exist=false;break;} //无解
x=(x+rec[i])%rec[i];b[i]=rec[i]/d;a[i]=qmul(x,hp[i]/d,b[i]); //真的x0推出b=rec/gcd(atk,rec)，a=x0
}
if(same){ //特判hp=rec
ll ans=ll(ceil(1.0*hp[]/atk[]));
for(int i=;i<=n;i++){
ll x=ceil(1.0*hp[i]/atk[i]),d=gcd(ans,x);
ans=ans/d*x;
}
printf("%lld\n",ans);continue;
}
if(!exist) continue;
ll ans=a[],mod=b[]; //开始EXCRT（以下模板，不解释，可以去我的另一个博客看）
for(int i=;i<=n;i++){
ll x,y,d=exgcd(mod,b[i],x,y),r=((a[i]-ans)%b[i]+b[i])%b[i],tmp=mod/d*b[i];
if(r%d){puts("-1");exist=false;break;}
x=(x+b[i])%b[i];x=qmul(x,r/d,b[i]);
ans=(qmul(mod,x,tmp)+ans)%tmp;
mod=tmp;
}
if(!exist) continue;
printf("%lld\n",ans); //终于没了
}
}
NOI2018D2T1_dragon（EXCRT）
终于啊……