代码

#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
typedef __int128 lll;
ll a[100005], p[100005], rw[100005];
static ll swords[100005];
static int ss[100005]; // sorted indices
static int cmp(const void *x, const void *y){ ll u=swords[*(int*)x], v=swords[*(int*)y]; return u<v?-1:u>v?1:0; }
ll egcd(ll x, ll y, ll *s, ll *t){
    if(!y){*s=1;*t=0;return x;}
    ll s1,t1,g=egcd(y,x%y,&s1,&t1);
    *s=t1; *t=s1-(x/y)*t1; return g;
}
int main(){
    int T; scanf("%d",&T);
    while(T--){
        int n,m; scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++) scanf("%lld",&a[i]);
        for(int i=0;i<n;i++) scanf("%lld",&p[i]);
        for(int i=0;i<n;i++) scanf("%lld",&rw[i]);
        for(int i=0;i<m;i++) scanf("%lld",&swords[i]);
        int cnt=m;
        for(int i=0;i<m;i++) ss[i]=i;
        // use a sorted multiset maintained via array of values
        qsort(ss,m,sizeof(int),cmp);
        ll *vals = malloc(sizeof(ll)*m);
        for(int i=0;i<m;i++) vals[i]=swords[ss[i]];
        // each dragon: find largest <= a_i else smallest
        ll ok = 1; ll mod = 1; ll rem = 0; ll lb = 0;
        ll atk_arr[100005];
        for(int i=0;i<n;i++){
            // binary search in vals[0..cnt)
            int lo=0, hi=cnt-1, pos=-1;
            while(lo<=hi){int mid=(lo+hi)>>1; if(vals[mid]<=a[i]){pos=mid;lo=mid+1;}else hi=mid-1;}
            if(pos<0) pos=0;
            ll atk=vals[pos];
            atk_arr[i]=atk;
            // erase vals[pos], insert rw[i]
            for(int j=pos;j<cnt-1;j++) vals[j]=vals[j+1];
            cnt--;
            // insert rw[i]
            lo=0; hi=cnt-1; pos=cnt;
            while(lo<=hi){int mid=(lo+hi)>>1; if(vals[mid]>=rw[i]){pos=mid;hi=mid-1;}else lo=mid+1;}
            for(int j=cnt;j>pos;j--) vals[j]=vals[j-1];
            vals[pos]=rw[i]; cnt++;
            // constraint: atk*x ≡ a (mod p)
            ll ai=a[i], pi=p[i];
            ll ce = (ai + atk - 1) / atk; if(ce>lb) lb=ce;
            if(pi==1) continue;
            ll g = egcd(atk, pi, &(ll){0}, &(ll){0}); // careful: need s,t
            {
                ll s,t; g = egcd(atk, pi, &s, &t);
                if(ai % g != 0){ ok=0; break; }
                ll p2 = pi/g, a2 = ai/g;
                // atk/g invertible mod p2: find inv
                ll s2,t2; egcd(atk/g, p2, &s2, &t2);
                ll b = ((lll)a2 * (s2 % p2 + p2) % p2 + p2) % p2;
                // merge: x ≡ b (mod p2), x ≡ rem (mod mod)
                if(mod==1 && rem==0 && 0){}
                ll s3,t3; ll g2 = egcd(mod, p2, &s3, &t3);
                ll diff = b - rem;
                if(diff % g2 != 0){ ok=0; break; }
                ll lcm = (lll)mod / g2 * p2;
                // x = rem + mod*k ≡ b (mod p2) → mod*k ≡ diff (mod p2)
                ll p3 = p2 / g2;
                ll k = ((lll)(diff / g2) * (s3 % p3 + p3) % p3 + p3) % p3;
                rem = (rem + (lll)mod * k) % lcm;
                mod = lcm;
            }
        }
        free(vals);
        if(!ok){ printf("-1\n"); continue; }
        // minimal x >= lb with x ≡ rem (mod mod)
        ll x = rem % mod; if(x<0) x+=mod;
        if(x < lb){
            ll k = (lb - x + mod - 1) / mod;
            x += k * mod;
        }
        printf("%lld\n", x);
    }
    return 0;
}

评测结果