P4774 [NOI2018]屠龙勇士

P4774 [NOI2018]屠龙勇士

---

先平衡树跑出打每条龙的atk t[]

然后每条龙有(xt equiv a[i]( ext{mod }p[i]))

就是(xt+kp[i]=a[i])

求出一个满足条件的(x_0)，通解是(x=x_0+k* ext{gcd}(t,p[i]))

就是(x equiv x_0 ( ext{mod } ext{gcd}(t,p[i])))

然后就有n个这样的式子，用excrt，合并方程

excrt懒得写了

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define vd void
#define int long long
il int gi(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int a[100010],p[100010],ATK[100010],Atk[100010],t[100010];
std::multiset<int>ST;
il int mult(int a,int b,int mod){
    if(llabs(a)<llabs(b))std::swap(a,b);
    if(b<0)b=-b,a=-a;
    int ret=0;
    while(b){
        if(b&1)ret=(ret+a)%mod;
        a=(a<<1)%mod;b>>=1;
    }
    return (ret+mod)%mod;
}
il int gcd(int a,int b){return b?gcd(b,a%b):a;}
il int exgcd(int a,int b,int&x,int&y){
    if(b==0){x=1,y=0;return a;}
    else{
        int ret=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return ret;
    }
}
il int inv(int a,int b){
    int x,y;exgcd(a,b,x,y);
    while(x<0)x+=b;
    return x;
}
int M[100010],Mod[100010];
main(){
    int T=gi(),n,m;
    while(T--){
        n=gi(),m=gi();
        for(int i=1;i<=n;++i)a[i]=gi();
        for(int i=1;i<=n;++i)p[i]=gi();
        for(int i=1;i<=n;++i)ATK[i]=gi();
        for(int i=1;i<=m;++i)Atk[i]=gi(),ST.insert(Atk[i]);
        for(int i=1;i<=n;++i){
            std::multiset<int>::iterator it=ST.upper_bound(a[i]);
            if(it==ST.begin())t[i]=*it;
            else --it,t[i]=*it;
            ST.erase(it);
            ST.insert(ATK[i]);
        }
        ST.clear();
        bool flg=1;
        for(int i=1;i<=n;++i)if(p[i]!=1)flg=0;
        if(flg){
            int ans=0;
            for(int i=1;i<=n;++i)ans=std::max(ans,(a[i]+t[i]-1)/t[i]);
            printf("%lld
",ans);
            continue;
        }
#define GG(a) {printf("%d
",a);goto ed;}
        for(int i=1;i<=n;++i){
            int x,y;
            int g=exgcd(t[i],p[i],x,y);
            if(a[i]%g)GG(-1);
            int P=p[i]/g;
            x=(x%P+P)%P;
            M[i]=mult(x,a[i]/g,P),Mod[i]=P;
        }
        {
            int lM=M[1],lMod=Mod[1];
            for(int i=2;i<=n;++i){
                int m1=lMod,m2=Mod[i],c1=lM,c2=M[i],g=gcd(m1,m2);
                if((c2-c1)%g)GG(-2);
                int m3,c3;
                m3=(m1/g*m2);
                c3=mult(mult(inv(m1/g,m2/g),(c2-c1)/g,m3)%(m2/g),m1,m3)+c1;
                c3=(c3%m3+m3)%m3;
                lM=c3,lMod=m3;
            }
            printf("%lld
",lM);
        }
        ed:;
    }
    return 0;
}