已经查明错误的地方,但不知道为何出错,也不知道如何修改 代码:
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
using namespace std; //预定义/预处理
#define inf 0x7fffffff
#define rg register
#define int long long
inline int read()
{
rg int x = 0;
rg int flag = 1;
rg char ch = getchar();
while(ch < '0' or ch > '9')
{
if(ch == '-')
flag = -1;
ch = getchar();
}
while(ch >= '0' and ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * flag;
}
inline void write(int x,char end='\n')
{
if(x==0)
{
putchar('0');
putchar(end);
return;
}
char F[205];
rg int tmp=x>0?x:-x ;
if(x<0)putchar('-') ;
int cnt=0 ;
while(tmp>0)
{
F[cnt++]=tmp%10+'0';
tmp/=10;
}
while(cnt>0) putchar(F[--cnt]);
putchar(end);
return;
}
inline void swap(int &x,int &y)
{
int i=x;
x=y;
y=i;
return;
}
inline int mul(int di,int mi,int mod)
{
int f=(di<0?-1:1);
f*=(mi<0?-1:1);
di=abs(di);
mi=abs(mi);
int an=0;
while(mi)
{
//write(mi);
if(mi&1)
an=(an+di)%mod;
mi>>=1;
di=(di+di)%mod;
}
return an*f;
}
#define ma 500005
int siz,child[ma][3],fa[ma],s[ma],v[ma],size[ma],tot;
#define root child[0][1]
inline void link(int x,int y,int pos)
{
//int z=y;
fa[x]=y;
child[y][pos]=x;
return;
}
inline int New(int w,int f,int pos)
{
int x=++tot;
v[x]=w;
link(x,f,pos);
size[x]=s[x]=1;
child[x][0]=child[x][1]=0;
return x;
}
inline void push_up(int i)
{
size[i]=
size[child[i][0]]+size[child[i][1]]+s[i];
return;
}
inline bool is(int i)
{
return i==child[fa[i]][0]? 0:1;
}
inline void roll(int i)
{
int y=fa[i];
int posy=is(y);
int pos=is(i);
int g=fa[y];
link(child[i][pos^1],y,pos);
link(y,i,pos^1);
link(i,g,posy);
push_up(y);
push_up(i);
return;
}
inline void splay(int now,int to=1)
{
to=fa[to];
while(fa[now]^to)
{
int x=fa[now];
if(fa[x]==to) roll(now);
else if(is(now)^is(x))
roll(now),roll(now);
else roll(x),roll(now);
}
return;
}
inline void ins(int val)
{
int now=root;
if(!siz)
{
New(val,root,1);
now=1;
}
else
while(1)
{
size[now]++;
if(v[now]==val)
{
s[now]++;
break;
}
int nxt=(val<v[now]? 0:1);
if(!child[now][nxt])
{
now=New(val,now,nxt);
//cout<<"ins "<<val<<" at "<<now<<endl;
break;
}
now=child[now][nxt];
}
splay(now,root);
siz++;
//cout<<"ins "<<val<<" at "<<now<<endl;
//cout<<"root size"<<size[root]
//<<" val "<<v[root]<<" s "
//<<s[root]<<endl;
}
inline int in(int val)
{
int x=root;
//cout<<"find "<<val<<' '<<root<<endl;
//for(int i=1;i<=tot;i++)
// cout<<i<<' '<<fa[i]<<' '<<v[i]<<' '<<is(i)<<endl;
while(1)
{
// cout<<"x= "<<x<<endl;
if(v[x]==val) return x;
int nxt =(val<v[x]? 0:1);
if(!child[x][nxt]) return x;
x=child[x][nxt];
}
}
inline void del(int x)
{
x=in(x);
if(x==-1) return;
siz--;
splay(x,root);
if(s[x]>1)
{
size[x]--;
s[x]--;
return;
}
int y=child[x][0];
if(!y)
{
root=child[x][1];
fa[root]=0;
return;
}
while(child[y][1])
y=child[y][1];
int r=child[x][1];
splay(y,child[x][0]);
link(r,y,1);
link(y,0,1);
root=y;
push_up(y);
return;
}
inline int getrank(int x)
{
int k=in(x);
if(x!=v[k]) return -1;
splay(k,root);
return size[child[root][0]]+1;
}
inline int lower(int x)
{
int u=x;
x=in(x);
if(v[x]<u) return v[x];
splay(x,root);
x=child[x][0];
if(!x) return -1;
while(child[x][1]) x=child[x][1];
return v[x];
}
inline int uper(int x)
{
int u=x;
x=in(x);
if(v[x]>u) return v[x];
splay(x,root);
//cout<<x<<endl;
x=child[x][1];
if(!x) return -1;
//cout<<x<<endl;
while(child[x][0]) x=child[x][0];
//cout<<x<<endl;
return v[x];
}
inline int kth(int k)
{
//cout<<"ask for "<<k<<" th num\n";
if(k>siz) return -1;
int x=root;
while(1)
{
int m=size[x]-size[child[x][1]];
if(size[child[x][0]]<k&&m>=k)
break;
if(m>k)
x=child[x][0];
else
x=child[x][1],k-=m;
}
splay(x,root);
//cout<<k<<" th num is In nod "<<x<<endl;
return v[x];
}
inline void clear()
{
while(siz) del(v[root]);
tot=0;
return;
}
int solve(int a,int b,int &x,int &y)
{
if(!b)
{
x=1;
y=0;
return a;
}
int k,gc;
gc=solve(b,a%b,x,y);
k=x;
x=y;
y=k-a/b*y;
return gc;
}
inline int CRT(int cnt,int b[],int a[],int &lcm)
{
int ans=a[1],m=b[1];
//printf("ans %lld m %lld\n",ans,m);
int x,y;
for(int i=2;i<=cnt;i++)
{
int k=((a[i]-ans)%b[i]+b[i])%b[i];
int z=solve(m,b[i],x,y);
if(k%z!=0) return -1;
x=mul(x,k/z,b[i]/z);
ans+=x*m;
m*=b[i]/z;
//ans=(ans%m+m)%m;
}
lcm=m;
return ans;
}
int a[ma],p[ma],ge[ma];
int use[ma],x[ma],y[ma];
inline int max(int x,int y)
{
return x>y?x:y;
}
inline int work()
{ int n=read(),m=read(),at;
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=n;i++)
p[i]=read();
for(int i=1;i<=n;i++)
ge[i]=read();
for(int i=1;i<=m;i++)
at=read(),ins(at);
int mi=0;
for(int i=1;i<=n;i++)
{
use[i]=lower(a[i]);
if(use[i]==-1) use[i]=uper(a[i]);
del(use[i]);
ins(ge[i]);
mi=max(mi,a[i]/use[i]+(a[i]%use[i]?1:0));
}
clear();
for(int i=1;i<=n;i++)
{
int hb=a[i];
int xx,yy;
int gc=solve(use[i],p[i],xx,yy);
int z=p[i]/gc;
if(hb%gc!=0)
{
//那6个点不应该在这里return -1
return -1;
}
x[i]=(mul(xx,hb/gc,z)+z)%z;
y[i]=z;
}
//for(int i=1;i<=n;i++)
// printf(" num = %lld %lld\n",x[i],y[i]);
int lcm;
int an=CRT(n,y,x,lcm);
//cout << "CRT" << endl;
if(an==-1) return an;
if(an>=mi) return an;
an=an+lcm*((mi-an)/lcm);
return an+lcm*(an<mi?1:0);
}
signed main()
{
int T=read();
while(T--) write(work());
}