#5 #6 #7 #18 #19 #20 WA 蒟蒻求助
查看原帖
#5 #6 #7 #18 #19 #20 WA 蒟蒻求助
220838
yql123456SN弱校小菜鸡楼主2020/5/21 20:09

已经查明错误的地方,但不知道为何出错,也不知道如何修改 代码:



#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());
}
2020/5/21 20:09
加载中...