代码

#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define LL long long
inline void Add(LL&x,LL y,LL z){
	x-=(x+=y)>=z?z:0;
}
inline LL mul(LL x,LL y,LL z){
	LL w=0;
	for(;y;y>>=1){
		if(y&1) Add(w,x,z);
		Add(x,x,z);
	}
	return w;
}
inline LL gcd(LL x,LL y,LL&a,LL&b){
	if(!y) return a=1,b=0,x;
	LL d=gcd(y,x%y,b,a);
	b-=x/y*a;
	return d;
}
int n,m,Atk1[100005],Atk2[100005];
LL A[100005],P[100005],B[100005];
multiset<LL> st;
multiset<LL>::iterator iter;
int main(){
	int Tests;
	scanf("%d",&Tests);
	while(Tests--){
		bool OK=1, pi1=1;
		st.clear();
		scanf("%d%d",&n,&m);
		F(i,1,n) scanf("%lld",A+i);
		F(i,1,n) scanf("%lld",P+i), P[i]>1?pi1=0:0;
		F(i,1,n) scanf("%d",Atk2+i);
		F(i,1,m) scanf("%d",Atk1+i), st.insert(Atk1[i]);
		F(i,1,n){
			iter=st.upper_bound(A[i]);
			if(iter!=st.begin()) --iter;
			B[i]=*iter;
			st.erase(iter); st.insert(Atk2[i]);
		}
		if(pi1){
			LL Ans=0;
			F(i,1,n){
				LL x=(A[i]-1)/B[i]+1;
				if(Ans<x) Ans=x;
			}
			printf("%lld\n",Ans);
			continue;
		}
		F(i,1,n){
			B[i]%=P[i]; A[i]%=P[i];
			LL d,x,y;
			d=gcd(B[i],P[i],x,y);
			B[i]/=d; P[i]/=d;
			if(A[i]%d) {OK=0; break;}
			A[i]/=d;
			x=(x%P[i]+P[i])%P[i];
			A[i]=mul(A[i],x,P[i]);
		}
		if(!OK) {puts("-1"); continue;}
		LL A0=0, P0=1;
		// x == A0 (mod P0)
		F(i,1,n){
			LL d,x,y,c=A[i]-A0;
			int f=1; if(c<0) f=-f, c=-c;
			d=gcd(P0,P[i],x,y);
			if(c%d) {OK=0; break;}
			x=(x%P[i]+P[i])%P[i];
			x=f*mul(x,c/d,P[i]);
			if(x<0) x+=P[i];
			A0=mul(x,P0,P0/d*P[i])+A0; P0=P0/d*P[i];
			A0%=P0;
		}
		if(!OK) {puts("-1"); continue;}
		printf("%lld\n",A0?A0:P0);
	}
	return 0;
}

评测结果