代码

#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
typedef long long ll;
const int N=100100;
multiset<ll> s;
int n,m,T;
ll h[N],aw[N],atk[N],x;
ll a[N],b[N],p[N],Fail;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if (b==0){x=1,y=0;return a;}
	ll x0,y0,ret=exgcd(b,a%b,x0,y0);
	x=y0,y=x0-(a/b)*y0;
	return ret;
}
ll gcd(ll a,ll b){
	if (b==0)return a;
	return gcd(b,a%b);
}
ll mul(ll a,ll b,ll mo){
	a=(a%mo+mo)%mo;b=(b%mo+mo)%mo;
	ll ans=0;
	while (b){
		if (b&1)ans=(ans+a)%mo;
		a=(a+a)%mo;
		b>>=1;
	}return ans;
}
void merge(int i,int j){
	ll b1=b[i],b2=b[j],p1=p[i],p2=p[j],k1,k2,g=gcd(p1,p2),L=(p1/g)*p2;
	if ((b2-b1)%g!=0){Fail=1;return;}
	exgcd(p1,p2,k1,k2);
	k1=mul(k1,(b2-b1)/g,L);
	b[i]=(b1+mul(k1,p1,L))%L,p[i]=L;
}
int main(){
for (scanf("%d",&T);T--;){
	scanf("%d%d",&n,&m);Fail=0;s.clear();
	for (int i=1;i<=n;i++)scanf("%lld",&h[i]);
	for (int i=1;i<=n;i++)scanf("%lld",&p[i]);
	for (int i=1;i<=n;i++)scanf("%lld",&aw[i]);
	for (int i=1;i<=m;i++)scanf("%lld",&x),s.insert(-x);
	for (int i=1;i<=n;i++){
		if (-(*--s.end())>h[i])atk[i]=-(*--s.end());
		else atk[i]=-(*s.lower_bound(-h[i]));
		s.erase(s.find(-atk[i]));
		a[i]=atk[i],b[i]=h[i];
		ll q=gcd(a[i],p[i]);
		if (b[i]%q!=0){Fail=1;break;}
		a[i]/=q,b[i]/=q,p[i]/=q;
		ll x,y;q=exgcd(a[i],p[i],x,y);
		x=(x%p[i]+p[i])%p[i];
		b[i]=mul(b[i],x,p[i]);
		s.insert(-aw[i]);
	}
	if (Fail){printf("-1\n");continue;}
	for (int i=2;i<=n;i++){
		merge(1,i);
		if (Fail)break;
	}
	if (Fail){printf("-1\n");continue;}
	ll ans=b[1],L=p[1];
	for (int i=1;i<=n;i++){
		ll al=(h[i]-1)/atk[i]+1;
		if (ans<al){
			ans=ans%L+(al/L)*L;
			while (ans-al>=L)ans-=L;
			while (ans<al)ans+=L;
		}
	}
	printf("%lld\n",ans);
}
return 0;}

评测结果