代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1e6;
int t,n,m;
LL a[N+10],p[N+10],atk[N+10];
struct data {
    LL x;
    int loc;
    bool operator < (const data &p) const {
        if (x!=p.x) return x<p.x;
        return loc<p.loc;
    }
};
set <data> s;
LL Find(LL x) {
    data now,ans;
    now.x=x;
    now.loc=1e9;
    set <data>::iterator it=s.lower_bound(now);
    if (it==s.begin()) {
        ans=*it;
        s.erase(it);
        return ans.x;
    }
    it--;
    ans=*it;
    s.erase(it);
    return ans.x;
}
LL gcd(LL x,LL y) {
    if (y==0) return x;
    return gcd(y,x%y);
}
void ex_gcd(LL a,LL b,LL &x,LL &y) {
    if (b==0) {
        x=1;
        y=0;
        return;
    }
    LL nowx,nowy;
    ex_gcd(b,a%b,nowx,nowy);
    x=nowy;
    y=nowx-a/b*nowy;
}
LL LCM(LL x,LL y) {
    LL d=gcd(x,y);
    return x/d*y;
}
LL multi(LL x,LL y,LL mod) {
    LL z=0;
    while (y) {
        if (y&1) z=(z+x)%mod;
        y>>=1;
        x=x*2%mod;
    }
    return z;
}
LL work(LL p1,LL a1,LL p2,LL a2) {
    LL d=gcd(p1,p2);
    if ((a2-a1)%d!=0) return -1;
    LL nowp1=p1/d,nowp2=p2/d;
    LL nowv=(a2-a1)/d;
    LL nowx,nowy;
    ex_gcd(nowp1,nowp2,nowx,nowy);
    nowx=(nowx%nowp2+nowp2)%nowp2;
    nowv=(nowv%nowp2+nowp2)%nowp2;
    nowx=multi(nowx,nowv,nowp2);
    LL lcm=LCM(p1,p2);
    nowx=((nowx*p1+a1)%lcm+lcm)%lcm;
    return nowx;
}
int main() {
    //freopen("dragon.in","r",stdin);
    //freopen("dragon.out","w",stdout);
    scanf("%d",&t);
    while (t--) {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
        for (int i=1;i<=n;i++) scanf("%lld",&p[i]);
        for (int i=1;i<=n;i++) scanf("%lld",&atk[i]);
        s.clear();
        for (int i=1;i<=m;i++) {
            data now;
            scanf("%lld",&now.x);
            now.loc=i;
            s.insert(now);
        }
        if (m==0) {
            printf("-1\n");
            continue;
        }
        LL lim=0,lcm=1,nowmod=0;
        bool judge=1;
        for (int i=1;i<=n;i++) {
            LL ki=Find(a[i]);
            data nowpv;
            nowpv.x=atk[i];
            nowpv.loc=m+i;
            s.insert(nowpv);
            lim=max(lim,(a[i]-1)/ki+1);
            a[i]%=p[i];
            LL d=gcd(p[i],ki);
            if (a[i]%d) {
                judge=0;
                break;
            }
            a[i]/=d;
            p[i]/=d;
            ki/=d;
            LL nowx,nowy;
            ex_gcd(ki,p[i],nowx,nowy);
            nowx=(nowx%p[i]+p[i])%p[i];
            nowx=multi(nowx,a[i],p[i]);
            nowmod=work(lcm,nowmod,p[i],nowx);
            if (nowmod==-1) {
                judge=0;
                break;
            }
            lcm=LCM(lcm,p[i]);
        }
        if (!judge) {
            printf("-1\n");
            continue;
        }
        nowmod=(nowmod%lcm+lcm)%lcm;
        nowmod+=lim/lcm*lcm;
        while (nowmod<lim) nowmod+=lcm;
        while (nowmod-lcm>=lim) nowmod-=lcm;
        printf("%lld\n",nowmod);
    }
    return 0;
}

评测结果