代码

#include<cstdio>
#include<set>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=100010;
multiset<ll> mts;
int t,n,m;
bool spec,exist,same;
ll hp[maxn],rec[maxn],a[maxn],b[maxn];
int award[maxn],atk[maxn];
ll qmul(ll a,ll b,ll mod){
    ll ans=0;
    for(;b;b>>=1,a=(a+a)%mod) if(b&1) ans=(ans+a)%mod;
    return ans;
}
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;
}
ll gcd(ll a,ll b){
    if(!b) return a;
    return gcd(b,a%b);
}
int main(){
    scanf("%d",&t);
    while(t--){
        spec=false;same=exist=true;
        mts.clear();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%lld",hp+i);
        for(int i=1;i<=n;i++){scanf("%lld",rec+i);if(rec[i]<hp[i]) spec=true;}
        for(int i=1;i<=n;i++) scanf("%d",award+i);
        for(int i=1;i<=m;i++){
            int x;
            scanf("%d",&x);
            mts.insert(x);
        }
        for(int i=1;i<=n;i++){
            multiset<ll>::iterator it;
            if(hp[i]<*mts.begin()) it=mts.begin();
            else it=mts.upper_bound(hp[i]),it--;
            atk[i]=*it;
            mts.erase(it);
            mts.insert(award[i]);
        }
        if(spec){
            ll ans=0;
            for(int i=1;i<=n;i++) ans=max(ans,ll(ceil(1.0*hp[i]/atk[i])));
            printf("%lld\n",ans);
            continue;
        }
        for(int i=1;i<=n;i++){
            if(!atk[i]){
                if(hp[i]==rec[i]){a[i]=0;b[i]=1;continue;}
                else{puts("-1");exist=false;break;}
            }
            if(hp[i]!=rec[i]) same=false;
            ll x,y,d=exgcd(atk[i],rec[i],x,y);
            if(hp[i]%d){puts("-1");exist=false;break;}
            x=(x+rec[i])%rec[i];b[i]=rec[i]/d;a[i]=qmul(x,hp[i]/d,b[i]);
        }
        if(same){
            ll ans=ll(ceil(1.0*hp[1]/atk[1]));
            for(int i=2;i<=n;i++){
                ll x=ceil(1.0*hp[i]/atk[i]),d=gcd(ans,x);
                ans=ans/d*x;
            }
            printf("%lld\n",ans);continue;
        }
        if(!exist) continue;
        ll ans=a[1],mod=b[1];
        for(int i=2;i<=n;i++){
            ll x,y,d=exgcd(mod,b[i],x,y),r=((a[i]-ans)%b[i]+b[i])%b[i],tmp=mod/d*b[i];
            if(r%d){puts("-1");exist=false;break;}
            x=(x+b[i])%b[i];x=qmul(x,r/d,b[i]);
            ans=(qmul(mod,x,tmp)+ans)%tmp;
            mod=tmp;
        }
        if(!exist) continue;
        printf("%lld\n",ans);
    }
}

评测结果