代码

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=100005;
multiset<ll>sword;
int T,n,m;
ll a[maxn],p[maxn],d[maxn],u[maxn];
vector<ll>aa,pp,uu,aaa,ppp,uuu; 
inline ll gcd(ll a,ll b) {
	return b?gcd(b,a%b):a;
}
inline ll lcm(ll a,ll b) {
	if(!a||!b)
		return a|b;
	return a/gcd(a,b)*b;
}
inline void exgcd(ll a,ll b,ll &d,ll &x,ll &y) {
	if(!b)
		d=a,x=1,y=0;
	else {
		exgcd(b,a%b,d,y,x);
		y-=x*(a/b);
	}
}
inline ll inv(ll v,ll p) {
	ll d,x,y;
	exgcd(v,p,d,x,y);
	return d==1?(x+p)%p:-1;
}
inline ll Mul(ll a,ll b,ll p) {
	ll res=0;
	while(b) {
		if(b&1) {
			res=res+a;
			if(res>=p)
				res-=p;
		}
		a=a+a;
		if(a>=p)
			a-=p;
		b>>=1;
	}
	return res;
}
inline bool work(ll a1,ll p1,ll a2,ll p2,ll &a3,ll &p3) {
	ll g=gcd(p1,p2),c=a2-a1;
	if(c%g)
		return 0;
	c=(c%p2+p2)%p2,c/=g,p1/=g,p2/=g,c=Mul(c,inv(p1,p2),p2),p3=p1*p2*g,a3=((Mul(c,p1*g,p3)+a1)%p3+p3)%p3;
	return 1;
}
inline ll solve() {
	if(!n)
		return 0;
	ll a1=a[1],p1=p[1],a2,p2;
	for(int i=2;i<=n;++i) {
		ll a3,p3;
		a2=a[i],p2=p[i];
		if(!work(a1,p1,a2,p2,a3,p3))
			return -1;
		a1=a3,p1=p3;
	}
	return (a1%p1+p1)%p1;
}
int main() {
	freopen("dragon.in","r",stdin);
	freopen("dragon.out","w",stdout);
	read(T);
	while(T--) {
		aa.clear(),uu.clear(),pp.clear();
		aaa.clear(),uuu.clear(),ppp.clear();
		sword.clear();
		read(n),read(m);
		int flg=1;
		for(int i=1;i<=n;++i)
			read(a[i]);
		for(int i=1;i<=n;++i)
			read(p[i]),flg&=(p[i]==1);
		for(int i=1;i<=n;++i)
			read(d[i]);
		for(int i=1,x;i<=m;++i)
			read(x),sword.insert(x);
		bool noans=0;
		for(int i=1;i<=n;++i) {
			multiset<ll>::iterator it=sword.upper_bound(a[i]);
			if(it==sword.begin())
				u[i]=*it,sword.erase(it);
			else
				--it,u[i]=*it,sword.erase(it);
			if(!u[i]) {
				puts("-1");
				noans=1;
				break;
			} 
			sword.insert(d[i]);
			ll g=gcd(p[i],u[i]);
			if(a[i]%g!=0) {
				puts("-1");
				noans=1;
				break;
			}
			a[i]/=g,u[i]/=g,p[i]/=g;
			if(a[i]%p[i]==0)
				aa.push_back(a[i]),uu.push_back(u[i]),pp.push_back(p[i]);
			else
				aaa.push_back(a[i]),uuu.push_back(u[i]),ppp.push_back(p[i]);
//			cout<<a[i]<<" "<<u[i]<<" "<<p[i]<<endl;
		}
		if(noans)
			continue;
		if(flg) {
			ll mx=0;
			for(int i=1;i<=n;++i)
				mx=max(mx,a[i]/u[i]+(a[i]%u[i]!=0));
			printf("%lld\n",mx);
			continue;
		}
		n=aaa.size();
		for(int i=1;i<=n;++i)
			a[i]=aaa[i-1],p[i]=ppp[i-1],u[i]=uuu[i-1];
		for(int i=1;i<=n;++i) {
			ll v=inv(u[i],p[i]);
			a[i]=Mul(a[i],v,p[i]);
		}
		ll now=solve();
		for(int i=0;i<(int)aa.size();++i) {
			ll l=lcm(uu[i],pp[i]);
			now=lcm(now,(aa[i]/l+(aa[i]%l!=0))*l/uu[i]);
		}
		printf("%lld\n",now);
	}
}

评测结果