代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define fo(i,a,b) for (i=a; i<=b; i++)
#define ll long long
using namespace std;

const int N=100005, M=1000000;
int t0, n, m, i, j, q0, h, t, p;
ll tot, ans;
ll a[N], b[N], c[N], d[N];
int bz[M+5];
bool flag;
int f[N*5], f2[N*5], l0[N*5], r0[N*5];

ll lcm(ll x,ll y)
{
	ll a=x, b=y, c=a%b;
	while (c) a=b, b=c, c=a%b;
	return x/b*y;
}

void extgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if (!b) d=a, x=1, y=0; else extgcd(b,a%b,d,y,x), y-=x*(a/b);
}
ll pd(ll a,ll n)
{
    ll d,x,y; extgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

void ins(int x,int l,int r)
{
	if (l==r) { f[x]=f2[x]=h; return; }
	int mid=(l+r)>>1;
	if (t<=mid)
	{
		if (!l0[x]) l0[x]=++q0; ins(l0[x],l,mid);
	}
	else
	{
		if (!r0[x]) r0[x]=++q0; ins(r0[x],mid+1,r);
	}
	if (!r0[x] || !f[r0[x]]) f[x]=f[l0[x]], f2[x]=f2[l0[x]]; else
	if (!l0[x] || !f[l0[x]]) f[x]=f[r0[x]], f2[x]=f2[r0[x]]; else
	f[x]=max(f[l0[x]],f[r0[x]]), f2[x]=min(f2[l0[x]],f2[r0[x]]);
}
void find(int x,int l,int r)
{
	if (l>=h && r<=t) { p=max(p,f[x]); return; }
	int mid=(l+r)>>1;
	if (mid>=h && l0[x]) find(l0[x],l,mid);
	if (mid<t && r0[x]) find(r0[x],mid+1,r); 
}
void find2(int x,int l,int r)
{
	if (l>=h && r<=t) { p=min(p,f2[x]); return; }
	int mid=(l+r)>>1;
	if (mid>=h && l0[x]) find2(l0[x],l,mid);
	if (mid<t && r0[x]) find2(r0[x],mid+1,r); 
}

void work(int x)
{
	int i, t, t1, t2; ll p, p1=0, p2=N*10;
	fo(i,1,m)
		if (d[i]<=a[x] && p1<d[i]) p1=d[i], t1=i; else
		if (d[i]>=a[x] && p2>d[i]) p2=d[i], t2=i;
	if (p1) p=p1%b[x], t=t1; else p=p2%b[x], t=t2;
	int k=pd(p,b[x]);
	if (k>0)
	{
		i=k*a[x]%b[x];
		while (i<=tot) bz[i]++, i+=b[x];
	}
	d[t]=c[x];
}

int main()
{
	scanf("%d",&t0);
	while (t0)
	{
		t0--, scanf("%d%d",&n,&m), ans=0, tot=1, flag=1;
		fo(i,1,n) scanf("%d",&a[i]);
		fo(i,1,n) 
		{
			scanf("%d",&b[i]), tot=lcm(tot,b[i]);
			if (b[i]!=1) flag=0;
		}
		fo(i,1,n) scanf("%d",&c[i]); 
		fo(i,1,m) scanf("%d",&d[i]); 
		if (n==1 && m==1)
		{
			j=pd(d[1],b[1]);
			if (j>0) ans=j*a[1]%b[1];
		}
		else
		if (flag)
		{
			if (m==1)
			{
				int j=d[1]; 
				fo(i,1,n) ans=max(ans,a[i]/j+(a[i]%j>0)), j=c[i];
			}
			else
			{
				q0=1;
				fo(i,1,m) h=t=d[i], ins(1,1,M);
				fo(i,1,n)
				{
					h=1, t=a[i], p=0, find(1,1,M);
					if (!p) h=a[i], p=t=M, find2(1,1,M);
					ans=max(ans,a[i]/p+(a[i]%p>0));
					h=0, t=p, ins(1,1,M);
					h=t=c[i], ins(1,1,M);
				}
			}
		}
		else
		{
			fo(i,1,n) work(i);
			fo(i,1,tot) if (bz[i]==n) { ans=i; break; }
			memset(bz,0,sizeof(bz));
		}
		if (ans) printf("%d\n",ans); else printf("-1\n");
	}
}

评测结果