代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
ll Mod(ll a,ll b)
{
	if(a>=0)	return a%b;
	else if(a%b==0)	return 0;
	else	return b+a%b;
}
/*
ll Div(ll a,ll b)
{
	if(a>=0)	return a/b;
	else if(a%b==0)	return a/b;
	else	return a/b-1;
}
#define B 1000000000
struct I
{
	ll a[4];
	I(){memset(a,0,sizeof(a));}
	I(ll x){a[0]=x;a[1]=a[2]=a[3]=0;work();}
	void work()
	{
		static ll i;
		for(i=0;i<3;i++)
		{
			a[i+1]+=Div(a[i],B);
			a[i]=Mod(a[i],B);
		}
	}
	ll to_ll()	{return a[0];}
	I &operator+=(const I &b)
	{
		static ll i;
		for(i=0;i<4;i++)	a[i]+=b.a[i];
		work();
	}
	I &operator-=(const I &b)
	{
		static ll i;
		for(i=0;i<4;i++)	a[i]-=b.a[i];
		work();
	}
};
I operator*(const I &a,const I &b)
{
	static ll i,j;I ans;
	for(i=0;i<4;i++)
		for(j=0;j<4-i;j++)
			ans.a[i+j]+=a.a[i]*b.a[j];
	ans.work();
	return ans;
}
*/
ll mul_mod(ll a,ll b,ll p)
{
	int flag=1;
	if(a<0)	flag*=-1,a=-a;
	if(b<0)	flag*=-1,b=-b;
	a%=p;b%=p;
	ll ans=0;
	for(;b;a=(a+a)%p,b>>=1)
		if(b&1)
			ans=(ans+a)%p;
	return Mod(ans*flag,p);
}
ll div_up(ll a,ll b)
{
	if(a<0)	return a/b;
	else if(a%b==0)	return a/b;
	else	return a/b+1;
}
void exgcd(ll a,ll b,ll &g,ll &x,ll &y)
{
	if(!b)	{x=1;y=0;g=a;}
	else	{exgcd(b,a%b,g,y,x);y-=x*(a/b);}
}
ll gcd(ll a,ll b)
{
	ll t;
	while(b)
	{
		t=a;
		a=b;
		b=t%b;
	}
	return a;
}
ll d;
ll ex_china(ll n,ll *a,ll *m)
{
	ll i,k1,k2,g,lm=m[1],la=Mod(a[1],m[1]),t;
	for(i=2;i<=n;i++)
	{
		exgcd(lm,m[i],g,k1,k2);
		if((a[i]-la)%g!=0)	return -1;
		t=m[i]/g;k1=mul_mod(k1,(a[i]-la)/g,t);t*=lm;
		la=Mod(mul_mod(k1,lm,t)+la,t);lm=t;
	}
	d=lm;
	return la;
}
multiset<ll> s;
ll a[100100],p[100100],t1[100100],b[100100],n,m;
ll xmin;
ll calc()
{
	ll i,g,x0,y0;
	for(i=1;i<=n;i++)
	{
		exgcd(b[i],p[i],g,x0,y0);
		if(a[i]%g!=0)	return -1;
		p[i]/=g;a[i]=mul_mod(x0,a[i]/g,p[i]);
	}
	return ex_china(n,a,p);
}
int main()
{
	freopen("dragon.in","r",stdin);
	freopen("dragon.out","w",stdout);
	ll i,t,T,k;
	multiset<ll>::iterator it;
	scanf("%lld",&T);
	while(T--)
	{
		s.clear();
		scanf("%lld%lld",&n,&m);
		for(i=1;i<=n;i++)	scanf("%lld",&a[i]);
		for(i=1;i<=n;i++)	scanf("%lld",&p[i]);
		for(i=1;i<=n;i++)	scanf("%lld",&t1[i]);
		for(i=1;i<=m;i++)	scanf("%lld",&t),s.insert(t);
		for(i=1;i<=n;i++)
		{
			it=s.upper_bound(a[i]);
			if(it==s.begin())	b[i]=*it;
			else	b[i]=*(--it);
			s.erase(s.find(b[i]));
			s.insert(t1[i]);
			if(i==1)	xmin=div_up(a[i],b[i]);
			else	xmin=max(xmin,div_up(a[i],b[i]));
		}
		t=calc();
		if(t!=-1)
		{
			k=div_up(xmin-t,d);
			if(k>=0)	t+=k*d;
		}
		printf("%lld\n",t);
	}
	return 0;
}

评测结果