代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <set>
#include <algorithm>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
typedef long long ll;
const int N = 100002;
template <class T>inline void read(T &x) {
    x=0; int f=1; char ch=getchar();
    while(!isdigit(ch)){if(f=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    x*=f;
}
inline ll mul(ll x,ll y,ll p) {
    ll res=x*y-(ll)((long double)x*y/p)*p;
    return res<0?res+p:res;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void exgcd(ll a,ll b,ll &x,ll &y) {
    if(b==0)x=1,y=0;
    else exgcd(b,a%b,y,x),y-=(a/b)*x;
}
ll inv(ll a,ll b) {ll x,y;exgcd(a,b,x,y);return (x+b)%b;}

int n, m;
ll a[N], p[N], z[N]; int c[N], v[N];

inline ll solve1() {
    ll ans=0;
    rep(i,1,n)	ans=max(ans,(a[i]-1)/v[i]+1);
    return ans;
}

inline ll solve() {
    rep(i,1,n) {
        ll A=v[i]%p[i], B=a[i]%p[i], g=gcd(A,p[i]);
        if(B%g)	return -1;
        A/=g, B/=g, p[i]/=g;
        z[i] = mul(inv(A,p[i]),B,p[i]);
    }
    rep(i,2,n) {
        ll g = gcd(p[i-1],p[i]);
        if((z[i]-z[i-1])%g)	return -1;
        ll x = mul(inv(p[i-1]/g,p[i]/g),(z[i]-z[i-1])/g,p[i]/g);
        ll d = p[i-1]/g*p[i];
        x=mul(x,p[i-1],d), z[i]=(x+z[i-1])%d, p[i]=d;
    }
    return z[n];
}

int main() {
//	freopen("dragon.in","r",stdin);
//	freopen("dragon.out","w",stdout);
    int T; read(T);
    while(T--) {
        read(n), read(m);
        rep(i,1,n)	read(a[i]);
        rep(i,1,n)	read(p[i]);
        rep(i,1,n)	read(c[i]);
        multiset<ll> s;
        multiset<ll>::iterator it;
        int w; rep(i,1,m)	read(w),s.insert(w);
        rep(i,1,n) {
            if(*s.begin()>=a[i])	v[i]=*s.begin(),s.erase(s.begin());
            else it=s.upper_bound(a[i]),v[i]=*--it,s.erase(it);
            s.insert(c[i]);
        }
        if(*(p+1)==1)	printf("%lld\n", solve1());
        else printf("%lld\n", solve());
    }
//	fclose(stdin);
//	fclose(stdout);
    return 0;
}

评测结果