很显然，每一步所选的剑和怪物都是确定的，可以先求出来（不用写平衡树，直接用multiset即可，注意删除要删指针，以下假设第i次攻击用ki攻击的剑，攻击第i只怪）

 首先判断无解，即如果存在ai使得gcd(ki,pi)不是ai的约数就无解，否则将ki、pi、ai同除gcd(ki,pi)，并用扩欧求出ki关于pi的逆元，移到右边

最终相当于求线性方程组的最小正整数解，用EXCRT即可

1 #include
2 using namespace std;
3 #define N 100005
4 #define ll long long
5 multisets;
6 multiset::iterator it;
7 int T,n,m;
8 ll x,y,sum,a[N],p[N],t[N];
9 bool flag;
10 ll exgcd(ll a,ll b,ll &x,ll &y){
11 if (!b){
12 x=1;
13 y=0;
14 return a;
15 }
16 ll t=exgcd(b,a%b,y,x);
17 y-=a/b*x;
18 return t;
19 }
20 ll mul(ll a,ll b,ll p){
21 if (!b)return 0;
22 ll s=mul(a,b>>1,p);
23 s=s*2%p;
24 if (b&1)s=(s+a)%p;
25 return s;
26 }
27 int main(){
28 scanf("%d",&T);
29 while (T--){
30 scanf("%d%d",&n,&m);
31 for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
32 for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
33 for(int i=1;i<=n;i++)scanf("%lld",&t[i]);
34 s.clear();
35 for(int i=1;i<=m;i++){
36 scanf("%lld",&x);
37 s.insert(x);
38 }
39 for(int i=1;i<=n;i++){
40 it=s.upper_bound(a[i]);
41 if (it!=s.begin())it--;
42 x=*it;
43 s.erase(it);
44 s.insert(t[i]);
45 t[i]=x;
46 }
47 flag=sum=0;
48 for(int i=1;i<=n;i++){
49 sum=max(sum,(a[i]-1)/t[i]);
50 ll d=exgcd(t[i],p[i],x,y);
51 if (a[i]%d){
52 flag=1;
53 break;
54 }
55 p[i]/=d;
56 a[i]=mul(a[i]/d,(x%p[i]+p[i])%p[i],p[i]);
57 }
58 for(int i=2;i<=n;i++){
59 ll d=exgcd(p[1],p[i],x,y);
60 if (a[1]%d!=a[i]%d){
61 flag=1;
62 break;
63 }
64 p[i]/=d;
65 a[1]+=mul((a[i]-a[1])/d,(x%p[i]+p[i])%p[i],p[i])*p[1];
66 p[1]*=p[i];
67 a[1]=((a[1]%p[1])+p[1])%p[1];
68 }
69 if (flag)printf("-1\n");
70 else
71 if (sum<a[1])printf("%lld\n",a[1]);
72 else printf("%lld\n",a[1]+(sum-a[1]+p[1])/p[1]*p[1]);
73 }
74 }