description
solution
主要算法是扩展中国剩余定理，但细节较多
快速乘
il ll upd(ll a,ll b,ll mod){return ((a+b)%mod+mod)%mod;}
il ll mul(ll a,ll b,ll mod){
RG ll ret=0;
if(b<0)a=-a,b=-b;
for(;b;b>>=1,a=upd(a,a,mod))
if(b&1)ret=upd(ret,a,mod);
return ret;
}
求同余方程的通解
需要注意同余方程(axequiv b(mod p))的通解
求出一个特解(x_0)后，应该有(x=x_0pmfrac{p}{g})
因此最后解出的同余方程应该是(xequiv x_0(mod frac{p}{g}))
il ll solvemod(ll a,ll b,ll &p,ll &r,ll &P){
ll x,y,g;
a=(a%p+p)%p;b=(b%p+p)%p;
Exgcd(a,p,x,y,g);
if(b%g)return -1;
x=(x%p+p)%p;P=p/g;
x=mul(b/g,x,P);
r=x;return 0;
}
扩展CRT
il ll exchina(ll *a,ll *b,ll *p,ll n,ll &L){
ll r1,lcm1,ri,lcmi,x,y,g;
if(solvemod(a[1],b[1],p[1],r1,lcm1)==-1)return -1;
for(RG int i=2;i<=n;i++){
if(solvemod(a[i],b[i],p[i],ri,lcmi)==-1)return -1;
Exgcd(lcm1,lcmi,x,y,g);
if((ri-r1)%g)return -1;
L=lcm(lcm1,lcmi);
r1=upd(r1,mul(mul((ri-r1)/g,x,L),lcm1,L),L);
lcm1=L;
}
return r1;
}
关于multiset中S.erase()的使用...
如果传的参是一个迭代器，那么只会删除当前迭代器对应的键值，
如果传的是一个数，那么set会删除里面所有的这个数...
code
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#define RG register
#define il inline
#define FILE "dragon"
using namespace std;
typedef long long ll;
typedef double dd;
const int N=100010;
const int inf=2147483647;
const ll INF=1e18+1;
il void file(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
}
il ll read(){
RG ll d=0,w=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')d=d*10+ch-48,ch=getchar();
return d*w;
}
//Case set
multiset<ll>S;
multiset<ll>::iterator tmp,pre;
il void geta(ll *b,ll *s,ll *k,int n,int m,ll *a){
S.clear();
for(RG int i=1;i<=m;i++)S.insert(s[i]);
for(RG int i=1;i<=n;i++){
tmp=S.begin();//printf("%lld,%lld
",*tmp,b[i]);
if((*tmp)>b[i]){a[i]=*tmp;S.erase(tmp);}
else{
tmp=S.upper_bound(b[i]);tmp--;
a[i]=*tmp;S.erase(tmp);
}
S.insert(k[i]);
}
}
//math
il ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
il ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
il void Exgcd(ll a,ll b,ll &x,ll &y,ll &g){
if(!b){g=a;x=1;y=0;return;}
Exgcd(b,a%b,y,x,g);y-=a/b*x;
}
il ll upd(ll a,ll b,ll mod){return ((a+b)%mod+mod)%mod;}
il ll mul(ll a,ll b,ll mod){
RG ll ret=0;
if(b<0)a=-a,b=-b;
for(;b;b>>=1,a=upd(a,a,mod))
if(b&1)ret=upd(ret,a,mod);
return ret;
}
il ll solvemod(ll a,ll b,ll &p,ll &r,ll &P){
ll x,y,g;
a=(a%p+p)%p;b=(b%p+p)%p;
Exgcd(a,p,x,y,g);
if(b%g)return -1;
x=(x%p+p)%p;P=p/g;
x=mul(b/g,x,P);
r=x;
return 0;
}
il ll exchina(ll *a,ll *b,ll *p,ll n,ll &L){
ll r1,lcm1,ri,lcmi,x,y,g;
if(solvemod(a[1],b[1],p[1],r1,lcm1)==-1)return -1;
for(RG int i=2;i<=n;i++){
if(solvemod(a[i],b[i],p[i],ri,lcmi)==-1)return -1;
Exgcd(lcm1,lcmi,x,y,g);
if((ri-r1)%g)return -1;
L=lcm(lcm1,lcmi);
r1=upd(r1,mul(mul((ri-r1)/g,x,L),lcm1,L),L);
lcm1=L;
}
return r1;
}
//input
int n,m;ll a[N],b[N],p[N],s[N],k[N],ans,ret,tot;
il void work(){
n=read();m=read();
for(RG int i=1;i<=n;i++)b[i]=read();
for(RG int i=1;i<=n;i++)p[i]=read();
for(RG int i=1;i<=n;i++)k[i]=read();
for(RG int i=1;i<=m;i++)s[i]=read();
geta(b,s,k,n,m,a);
ans=exchina(a,b,p,n,tot);
if(ans==-1){puts("-1");return;}
ret=0;for(RG int i=1;i<=n;i++)ret=max(ret,(b[i]+a[i]-1)/a[i]);
ans=ans+ret/tot*tot+(ret%tot>ans)*tot;
printf("%lld
",ans);
}
int main()
{
RG int T=read();
while(T--)
work();
return 0;
}