代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> p;
#define int long long
const int N=100010;
long long a[N],pp[N],loweex;
int hh[N],ha[N],att[N];
const p Z=p(-1,-1);
namespace Sub8_13{
	long long m;
	ll MUL(ll x,ll y,ll m){
//		if (x==-7855686399317862242ll) cerr<<y<<" "<<m<<endl;
		x=(x%m+m)%m; y=(y%m+m)%m;
//		cerr<<"MUL"<<x<<" "<<y<<" "<<m<<endl;
		ll ret=0;
		for (; y; y>>=1,x=(x+x)%m){
			if (y&1) ret=(ret+x)%m;
//			if (d) cerr<<ret<<" "<<x<<" "<<y<<endl; 
		} 
		return ret;
	}
	void ex_gcd(ll a,ll &x,ll b,ll &y){//only for ll a>b
//		cerr<<"ex_gcd"<<a<<" "<<x<<" "<<b<<" "<<y<<" "<<m<<endl;
		if (b==0){
			x=1;
			y=0;
			return;
		}
		ll xx,yy;
		ex_gcd(b,xx,a%b,yy);
		x=yy;
		y=xx-a/b*yy;
//		cerr<<x<<" "<<y<<endl;
	}
	p Chinese_remainder_theorem(p x,p y){
//		cerr<<"C"<<x.first<<" "<<x.second<<" "<<y.first<<" "<<y.second<<endl;
		if (x.second>y.second) swap(x,y);
		ll gcd=__gcd(x.first,y.first);
		if ((y.second-x.second)%gcd!=0) return Z;
		long long lcm=x.first/gcd*y.first; m=lcm;
//		if (d) cerr<<lcm<<endl;
		long long k1,k2;
			ex_gcd(x.first,k1,y.first,k2);
//		if (d) cerr<<lcm<<endl;
			k2=-k2;
			k1=k1*((y.second-x.second)/gcd)%m;
			k2=k2*((y.second-x.second)/gcd)%m;
//		if (d) cerr<<k1<<" "<<k2<<" "<<x.first<<" "<<endl;
		return p(lcm,((MUL(k1,x.first,lcm)+x.second)%lcm+lcm)%lcm);
	}
}
signed main(){
	freopen("dragon.in","r",stdin); freopen("dragon.out","w",stdout);
	/*p t=Sub8_13::Chinese_remainder_theorem(p(15,8),p(7,2));
	cerr<<t.first<<" "<<t.second<<endl;
	return 0;*/
	int t; scanf("%lld",&t);
	while (t--){
		int n,m; scanf("%lld%lld",&n,&m);
//		cerr<<n<<" "<<m<<endl;
		for (int i=1; i<=n; ++i) scanf("%lld",&a[i]);
		for (int i=1; i<=n; ++i) scanf("%lld",&pp[i]);
		for (int i=1; i<=n; ++i) scanf("%lld",&hh[i]);
		multiset<int> s;
		for (int i=1; i<=m; ++i) scanf("%lld",&ha[i]),s.insert(ha[i]);
//		if (n==1&&m==1) cout<<a[1]<<" "<<p[1]<<" "<<ha[1]<<endl;
		loweex=0;
		for (int i=1; i<=n; ++i){
			multiset<int>::iterator j=s.upper_bound(a[i]);
			if (j!=s.begin()) --j;
			att[i]=(*j);
			loweex=max(loweex,(a[i]-1)/att[i]+1);
			s.erase(j);
			s.insert(hh[i]);
		}
		vector<p> gv;
		for (int i=1; i<=n; ++i){
			ll x1,x2;
			ll g=__gcd((ll)att[i],pp[i]);
			if (a[i]%g){
//				cerr<<i<<" "<<a[i]<<" "<<g<<" "<<att[i]<<" "<<pp[i]<<endl;
				puts("-1");
				break;
			}
//			if (i==7||i==8) cerr<<i<<" "<<att[i]/g<<" "<<pp[i]/g<<endl;
			Sub8_13::ex_gcd(att[i]/g,x1,pp[i]/g,x2);
//			if (i==7||i==8) cerr<<att[i]/g<<" "<<x1<<" "<<pp[i]/g<<" "<<x2<<endl;
			ll dnum=a[i]/g;
			gv.push_back(p(pp[i]/g,Sub8_13::MUL(x1,dnum,pp[i]/g)));
			((gv.back().second%=gv.back().first)+=gv.back().first)%=gv.back().first; 
//			cerr<<gv.back().first<<" "<<gv.back().second<<endl;
		}
//		cerr<<"!!!";
		if ((int)gv.size()<n) continue;
		p ret=gv[0];
		for (size_t i=1; i<gv.size(); ++i){
//			if (i==2||i==3) cerr<<i<<" "<<ret.first<<" "<<ret.second<<" "<<gv[i].first<<" "<<gv[i].second<<endl;
			ret=Sub8_13::Chinese_remainder_theorem(ret,gv[i]);
			if (ret==Z){
				puts("-1");
				break;
			}
		}
		if (ret==Z) continue; 
//		cerr<<ret.first<<" "<<ret.second<<endl;
		if (ret.second<loweex){
			ll t=((loweex-1)/ret.first+1)*ret.first;
			if (t-ret.first+ret.second>=loweex) ret.second=t-ret.first+ret.second;
			else ret.second=t+ret.second;
		}
		printf("%lld\n",ret.second);
	}
}

评测结果