代码

#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
#define rt register int
#define l putchar('\n')
#define ll long long
#define r read()
using namespace std;
namespace fast_IO
{
    const int IN_LEN=10000000,OUT_LEN=10000000;
    char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;
    inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
    inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}
    inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
inline ll read(){
    register ll x = 0; char zf = 1; char ch;
    while (ch != '-' && !isdigit(ch)) ch = getchar();
    if (ch == '-') zf = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}
void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}
void writeln(const ll y){write(y);putchar('\n');}
int i,j,k,m,n,x,y,z,cnt,fla;
ll a[200010],p[200010],jl[200010],use[200010];
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,y,x);y-=a/b*x;
}
inline ll mul(ll x, ll y, ll mod){
	ll tmp=(x*y-(ll)((long double)x/mod*y+1e-8)*mod);
	return tmp<0 ? tmp+mod : tmp;
}
ll inv(ll A,ll p){
    if(p==1)return 0;
    ll x,y;
    exgcd(A,p,x,y);
    if(x<0)x+=p;
    /*if(x*A%p!=1){
        fla=1;
        return 1;
    }*/
    return x;
}
ll gcd(ll x,ll y){
    return !y?x:gcd(y,x%y);
}
void excrt(ll m1,ll c1,ll m2,ll c2,ll &m,ll &c){
    ll GCD=gcd(m1,m2);
    if((c2-c1)%GCD){
        fla=1;
        return;
    }
    m=m1/GCD*m2;
    c=mul(mul(inv(m1/GCD,m2/GCD),(c2-c1)/GCD,m2/GCD),m1,m)+c1;
    while(c<0)c+=m;
    //while(c<0)c+=m;//if(m<0)cout<<m1<<' '<<c1<<' '<<m2<<' '<<c2<<' '<<m<<' '<<c<<endl;
}

void check(){
    //use[i]*x== a[i]+kp[i]
    ll least=0;
    //writeln(a[1]);writeln(p[1]);
    for(rt i=1;i<=n;i++){
        least=max(least,(a[i]%use[i]==0)?a[i]/use[i]:a[i]/use[i]+1);
        ll GCD=gcd(use[i],p[i]);
        if(a[i]%GCD){
            puts("-1");
            return;
        }
        use[i]/=GCD;
        p[i]/=GCD;
        a[i]/=GCD;
        a[i]=mul(a[i],inv(use[i],p[i]),p[i]);
    }
    ll ans1=p[1],ans2=a[1],G1,G2;
    for(rt i=2;i<=n;i++){
        if(p[i]==1)continue;
        fla=0;
        excrt(ans1,ans2,p[i],a[i],G1,G2);
        if(fla==1){
            puts("-1");
            return;
        }
        ans1=G1,ans2=G2;
    }
    ans2%=ans1;
    if(ans2<least)ans2+=ans1*((least-ans2-1)/ans1+1);
    writeln(ans2);//exit(0);
}
multiset<ll>s;
multiset<ll>::iterator it;
int main(){
    for(rt t=r;t;t--){
        s.clear();	
        n=r;m=r;fla=0;
        for(rt i=1;i<=n;i++)a[i]=r;
        for(rt i=1;i<=n;i++)p[i]=r;
        for(rt i=1;i<=n;i++)jl[i]=r;
        for(rt i=1;i<=m;i++){
            x=r;
            s.insert(x);
        }
        for(rt i=1;i<=n;i++){
            if(*s.begin()>a[i])use[i]=*s.begin();
            else {
                it=s.upper_bound(a[i]);
                it--;
                use[i]=*it;
            }
            s.erase(s.find(use[i]));
            s.insert(jl[i]);
        }
        check();
    }
    return 0;
}

评测结果