代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define MN 500005
using namespace std;
typedef long long ll;
int n,m,T;ll lif[MN],hea[MN],atk[MN],afatk[MN],patk[MN];
multiset<ll>st;
multiset<ll>::iterator it;
void add(ll &x,ll y,ll mod){(x+=y)>=mod?x-=mod:0;}
ll mul(ll x,ll y,ll mod){
	ll tmp=0;
	while(y){
		if(y&1)add(tmp,x,mod);
		add(x,x,mod);y>>=1;
	}return tmp;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){x=1,y=0;return a;}
	ll d=exgcd(b,a%b,x,y),tmp=x;x=y,y=tmp-a/b*x;
	return d;
}
int main(){
	freopen("dragon19.in","r",stdin);
	freopen("dragon.out","w",stdout);
	scanf("%d",&T);ll x,y;
	while(T--){
		scanf("%d%d",&n,&m);st.clear();bool fd=1;
		for(int i=1;i<=n;i++)scanf("%lld",&lif[i]);
		for(int i=1;i<=n;i++)scanf("%lld",&hea[i]),fd&=(hea[i]==1);
		for(int i=1;i<=n;i++)scanf("%lld",&afatk[i]);
		for(int i=1;i<=m;i++)scanf("%lld",&patk[i]),st.insert(patk[i]);
		for(int i=1;i<=n;i++){
			it=st.upper_bound(lif[i]);if(it!=st.begin())--it;
			atk[i]=(*it);st.erase(it);st.insert(afatk[i]);
		}
		if(fd){
			ll ans=0; 
			for(int i=1;i<=n;i++)ans=max(ans,(lif[i]-1)/atk[i]+1);
			printf("%lld\n",ans);
		}else {
			bool OK=1;
			for(int i=1;i<=n;i++){//atk[i]*x=lif[i] (mod hea[i])
				atk[i]%=hea[i],lif[i]%=hea[i];
				ll tmp=exgcd(atk[i],hea[i],x,y);
				atk[i]/=tmp,hea[i]/=tmp;
				if(lif[i]%tmp){OK=0;break;}
				lif[i]/=tmp;x=(x%hea[i]+hea[i])%hea[i];
				lif[i]=mul(lif[i],x,hea[i]);
			}if(!OK){puts("-1");continue;}ll ansl=0,ansp=1;
			for(int i=1;i<=n;i++){//x=ansl (mod ansp),x=lif[i] (mod hea[i]) --> ansp*k1+ansl=hea[i]*k2+lif[i] -->ansp*x-hea[i]*y=lif[i]-ansl 
				ll c=lif[i]-ansl;int f=c<0?-1:1;c=abs(c);
				ll tmp=exgcd(ansp,hea[i],x,y);
				if(c%tmp){OK=0;break;}x=(x%hea[i]+hea[i])%hea[i],x=f*mul(x,c/tmp,hea[i]);x=(x%hea[i]+hea[i])%hea[i];
				ansl=(mul(x,ansp,ansp/tmp*hea[i])+ansl)%(ansp/tmp*hea[i]),ansp*=hea[i]/tmp;//printf("%lld %lld\n",ansl,ansp);
			}if(!OK)puts("-1");else printf("%lld\n",ansl?ansl:ansp);
		}
	}
}

评测结果