博客

题目链接：

BZOJ

，[洛谷](

https://www.luogu.org/problemnew/show/P4774

0)

---

对于每条龙，我们可以算出攻击次数

\(x_i\)

，满足方程

\(x_i\equiv Z_i(\%R_i)\)

，

\(R_i=\dfrac{p_i}{\gcd(p_i,ATK_i)}\)

，

\(Z_i\)

则为首次将巨龙杀死的攻击次数（

\(Z_i\)

可能大于

\(R_i\)

，但是不能

\(\%\)

掉）

然后我们就可以用ex_crt将所有方程合并起来

最后求出的解

\(X\)

可能

\(<\max\limits_{i=1}^m\{Z_i\}\)

，那么我们就把

\(X\)

不断加

\(lcm(R_1,R_2,…R_m)\)

，直到满足即可

/*program from Wolfycz*/
#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef std::multiset<ll> msi;
typedef unsigned long long ull;
inline char gc(){
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>inline T frd(T x){
    int f=1; char ch=gc();
    for (;ch<'0'||ch>'9';ch=gc())   if (ch=='-')    f=-1;
    for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}
template<typename T>inline T read(T x){
    int f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}
inline void print(int x){
    if (x<0)    putchar('-'),x=-x;
    if (x>9)    print(x/10);
    putchar(x%10+'0');
}
template<typename T>inline T min(T x,T y){return x<y?x:y;}
template<typename T>inline T max(T x,T y){return x>y?x:y;}
template<typename T>inline T swap(T &x,T &y){T t=x; x=y,y=t;}
const int N=1e5;
namespace Math{
    ll mul(ll _a,ll _b,ll _p){
        ll _c=(ld)_a*_b/_p+0.5;
        ll _ans=_a*_b-_c*_p;
        if (_ans<0) _ans+=_p;
        return _ans;
    }
    ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
    void exgcd(ll a,ll b,ll &x,ll &y){
        if (!b){x=1,y=0;return;}
        exgcd(b,a%b,x,y);
        ll t=x; x=y,y=t-a/b*y;
    }
    ll Ex_GCD(ll a,ll b,ll c){
        ll d=gcd(a,b),x,y;
        if (c%d)    return -1;
        a/=d,b/=d,c/=d;
        exgcd(a,b,x,y);
        x=(mul(x,c,b)+b)%b;
        if ((c-a*x)/b>0)    x+=b;
        return x;
    }
    ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
}
msi Sw;//Sword
ll h[N+10],Z[N+10],p[N+10],R[N+10];
int V[N+10];
// x = Zi ( % Ri )
using namespace Math;
int main(){
    for (int T=read(0);T;T--){
        Sw.clear();
        int n=read(0),m=read(0); ll Max=0;
        for (int i=1;i<=n;i++)  h[i]=read(0ll);
        for (int i=1;i<=n;i++)  p[i]=read(0ll);
        for (int i=1;i<=n;i++)  V[i]=read(0);
        for (int i=1;i<=m;i++)  Sw.insert(read(0));
        bool Wrong=0;
        for (int i=1;i<=n;i++){
            msi::iterator it=Sw.upper_bound(h[i]);
            if (it!=Sw.begin()) it--;
            Z[i]=h[i]/(*it),h[i]%=*it;
            ll tmp=Ex_GCD(*it,p[i],h[i]);
            if (tmp==-1){Wrong=1;break;}
            Z[i]+=tmp,R[i]=p[i]/Math::gcd(*it,p[i]);
            Sw.erase(it),Sw.insert(V[i]);
            Max=max(Max,Z[i]);
        }
        if (Wrong){
            printf("-1\n");
            continue;
        }
        ll Z1=Z[1],R1=R[1];
        for (int i=2;i<=n;i++){
            ll tmp=Ex_GCD(R1,R[i],Z[i]-Z1);
            if (tmp==-1){
                Wrong=1;
                break;
            }
            ll Lcm=lcm(R1,R[i]);
            Z1=(Z1+mul(tmp,R1,Lcm))%Lcm,R1=Lcm;
        }
        if (Wrong){
            printf("-1\n");
            continue;
        }
        ll Ans=Ex_GCD(1,R1,Z1);
        if (Ans<Max)    Ans+=R1*((Max-Ans-1)/R1+1);
        printf("%lld\n",Ans);
    }
    return 0;
}