题目大意：
首先我们应该可以看出这是一道(excrt)题目
至于剑这个限制其实很(naive)，用(multiset)存一下就好了
根据题意我们可以列出方程组
[egin{cases}d_1xequiv a_1 (mod p_1)\d_2xequiv a_2 (mod p_2)\……\d_nxequiv a_n (mod p_n)end{cases}
]
其中(d_i)为剑攻击力，(x)为攻击次数，(a_i)为龙龙的血量，(p_i)为回复能力
毒瘤
但是我们好像有(a_i>p_i)的情况……根据题目我们好像不能直接模掉……
然而我们翻过题解之后发现可能存在(a_i>p_i)时，全部满足(p_i=1)那么我们大力判断掉就好了
具体方法：
[ans=max{ lceilfrac{d_i}{a_i}
ceil }
]
通解
先考虑(d_ixequiv a_i (mod p_i))好像和一般的(crt)方程不太一样，化简一下
[x*d_i+y*p_i=- a_i
]
用(exgcd)求出一组(x_t,y_t)
由于(ecgcd)通解为(x=x_t+k*frac{b}{gcd(a,b)})，得到(x=x_t+k*frac{p_i}{gcd(p_i,d_i)})
对(frac{p_i}{gcd(p_i,d_i)})取模，得到
(xequiv x_t (mod frac{p_i}{gcd(p_i,d_i)}))
然后大力(excrt)
注意
我们感性理解一下可以得出(xge (maxn=max{lceilfrac{a_i}{d_i} ceil}))，如果最后答案小于这个数，应该补上
推出来是(ret=ret+m*lceilfrac{maxn-ret}{m} ceil)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define eps (1e-8)
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=1e5+10;
int haku;
int n,m;
int a[N],p[N],sword[N];
inline void exgcd(int &x,int &y,int &g,int a,int b)
{
if(!b){x=1,y=0,g=a;return;}
exgcd(y,x,g,b,a%b);
y-=a/b*x;
}
inline int slow(int x,int k,int p)
{
int ret=0;
while(k)
{
if(k&1) ret=(ret+x)%p;
x=(x+x)%p;
k>>=1;
}
return ret;
}
multiset<int> q;
multiset<int>::iterator it;
inline int excrt()
{
int m=1,ret=0,maxn=0,x,y,g;
for(int i=1;i<=n;++i)
{
it=q.upper_bound(a[i]);
if(it!=q.begin()) --it;
int k=*it;
q.erase(it);
q.insert(sword[i]);
maxn=max(maxn,(a[i]-1)/k+1);
k%=p[i],a[i]%=p[i];
exgcd(x,y,g,k,p[i]);
if(a[i]%g) return -1;
p[i]/=g;
a[i]=slow(a[i]/g,(x%p[i]+p[i])%p[i],p[i]);
int c=((a[i]-ret)%p[i]+p[i])%p[i];
exgcd(x,y,g,m,p[i]);
if(c%g) return -1;
x=slow(x,c/g,p[i]);
ret+=x*m;
m*=p[i]/g;
ret%=m;
}
return ret>=maxn?ret:ret+m*((maxn-ret-1)/m+1);
}
inline void main()
{
haku=read();
while(haku--)
{
n=read(),m=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i) p[i]=read();
for(int i=1;i<=n;++i) sword[i]=read();
for(int i=1;i<=m;++i) q.insert(read());
printf("%lld
",excrt());
q.clear();
}
}
}
signed main()
{
red::main();
return 0;
}