代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>

#define int __int128
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
#define lc (x<<1)
#define rc (x<<1|1)
#define max Max
#define min Min
#define abs Abs

using namespace std;

inline int read()
{
	int ans=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=(ans<<1)+(ans<<3)+c-'0';c=getchar();}
	return ans*f;
}

inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x/10) write(x/10);
	putchar((char)(x%10)+'0');
}

template<typename T>inline T Abs(T a){return a>0?a:-a;};
template<typename T,typename TT>inline T Min(T a,TT b){return a>b?b:a;}
template<typename T,typename TT> inline T Max(T a,TT b){return a>b?a:b;}

const int N=2e5+5;
int t,n,m,a[N],b[N],c[N],p[N],ok[N];

multiset<int> s;
multiset<int>::iterator it;

inline int exgcd(int a,int b,int &x,int &y);
inline int solve(int a,int b,int c,int p);

signed main()
{
	//freopen("yangli.in","r",stdin);
	t=read();
	while(t--)
	{
		n=read();m=read();
		s.clear();
		int fll=1,flll=1;
		for(int i=1;i<=n;++i) a[i]=read(),ok[i]=1;
		for(int i=1;i<=n;++i) p[i]=read(),fll=(fll==1&&p[i]==1?1:0),flll=(flll==1&&p[i]==a[i]?1:0);
		for(int i=1;i<=n;++i) b[i]=read();
		for(int i=1;i<=m;++i) s.insert(read());
		for(int i=1;i<=n;++i)
		{
			it=--s.upper_bound(a[i]);
			if(it==s.end()) it=s.begin();
			c[i]=*it;s.erase(it);
			s.insert(b[i]);
		}
		if(fll)
		{
			int res=0;
			for(int i=1;i<=n;++i)
				res=max(res,(int)ceil(a[i]/(c[i]+0.0)));
			write(res);putchar('\n');
			continue;
		}
		if(flll)
		{
			int res=1;
			for(int i=1;i<=n;++i)
			{
				int tmp=p[i]/__gcd(p[i],c[i]);
				res=res/__gcd(res,tmp)*tmp;
			}
			write(res);putchar('\n');
			continue;
		}
		int fl=1;
		for(int i=1;i<=n;++i)
			if(a[i]==p[i])
			{
				if(c[i]==p[i]){fl=0;break;}
				ok[i]=0;
			} 
		if(!fl)
		{
			printf("-1\n");
			continue;
		}
		for(int i=1;i<=n;++i)
			if(ok[i])
			{
				c[i]%=p[i];
				int gcd=__gcd(c[i],p[i]);
				int x=solve(c[i],p[i],a[i],p[i]/gcd);
				if(x==-1){fl=0;break;}
				a[i]=x;p[i]/=gcd;
			}
		if(!fl)
		{
			printf("-1\n");
			continue;
		}
		int A=a[1],P=p[1];
		for(int i=2;i<=n;++i)
			if(ok[i])
			{
				int gcd=__gcd(P,p[i]);
				int x=solve(P,p[i],a[i]-A,P/gcd*p[i]);
				if(x==-1){fl=0;break;}
				A=(x*P+A)%(P/gcd*p[i]);
				P=P/gcd*p[i];
			}
		if(!fl)
		{
			printf("-1\n");
			continue;
		}
		write(A);putchar('\n');
	}
	return 0;
}

inline int exgcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1;y=0;
		return a;
	}
	int tmp=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return tmp;
}

inline int solve(int a,int b,int c,int p)
{
	int x,y,gcd=exgcd(a,b,x,y);
	if(c%gcd!=0) return -1;
	x=((x*c/gcd)%p+p)%p;
	if(x<0) x-=p;
	return x;
}

评测结果