Luogu

LOJ

分析

显然用来打每条龙的剑是确定的，可以用 std::multiset 预处理出来。假设打第 $i$ 条龙的剑的攻击力为 $atk_i$。

那么如果一个 $x$ 满足条件，则应有
$$
x\times atk_i\equiv a_i\pmod{p_i}
$$
但这并不够，我们还需要保证解出来的 $x$ 能将所有龙的血量减到 $0$，即要有 $x\geq\left\lceil\frac{a_i}{atk_i}\right\rceil$。我们只需要解出一个解后加到满足条件即可。

现在考虑怎么解这个同余方程组。因为 $x$ 带了一个系数所以不能直接 CRT，我们要想办法把系数去掉。

考虑解不定方程 $atk_ix+p_iy=a_i$，设一个满足条件的 $x$ 为 $x_0$，则这个方程可以化为
$$
x\equiv x_0\pmod{\frac{p_i}{\gcd(atk_i,p_i)}}
$$
这样子就可以直接 exCRT 了。

需要注意的是 $a_i\leq 10^{12}$，所以需要写慢速乘。

代码

//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m;
ll lim,a[N],p[N],sw[N],atk[N];
multiset<ll> S;

ll qmul(ll a,ll b,ll mod) { ll c=0;
    for (;b;b>>=1,a=(a+a)%mod) if (b&1) c=(c+a)%mod;
    return c;
}

ll exgcd(ll a,ll b,ll& x,ll& y) {
    if (!b) { x=1,y=0; return a; }
    ll d=exgcd(b,a%b,y,x); y-=a/b*x;
    return d;
}

namespace CRT {
    ll a[N],b[N];
    ll main() {
        ll ans=a[1],M=b[1];
        for (int i=2;i<=n;++i) {
            ll c=(a[i]-ans%b[i]+b[i])%b[i];
            ll x,y,d=exgcd(M,b[i],x,y);
            if (c%d) return -1;
            x=qmul(x,c/d,b[i]),ans+=M*x,M*=b[i]/d,ans=(ans+M)%M;
        }
        return ans>=lim?ans:ans+M*(ll)(ceil(1.0*(lim-ans)/M)+0.5);
    }
}

ll solve() {
    for (int i=1;i<=n;++i) {
        ll x,y,d=exgcd(atk[i],p[i],x,y);
        if (a[i]%d) return -1;
        x=(qmul(x,a[i]/d,p[i]/d)+p[i]/d)%(p[i]/d);
        CRT::a[i]=x,CRT::b[i]=p[i]/d;
    }
    return CRT::main();
}

int main() {
    int T=read();
    while (T--) {
        S.clear(),lim=0;
        n=read(),m=read();
        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) sw[i]=read();
        for (int i=1;i<=m;++i) S.insert(read());
        for (int i=1;i<=n;++i) {
            auto it=S.upper_bound(a[i]);
            if (it!=S.begin()) --it;
            atk[i]=*it,S.erase(it),S.insert(sw[i]);
            lim=max(lim,(ll)(ceil(1.0*a[i]/atk[i])+0.5));
        }
        printf("%lld\n",solve());
    }   
    return 0;
}