代码

#include<set>
#include<cstdio>
#define ll long long
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;

const int N = 2e5 + 5;

const ll inf = - (1LL << 62);

int T, n, m, q;
ll a[N], p[N], v1[N], v2[N];

struct node {
	ll a, p;
} b[N];

multiset<ll> s;

ll mx, ans;

ll gcd(ll x, ll y) {return !y ? x : gcd(y, x % y);}

ll x1, y1;

void exgcd(ll a, ll b) {
	if(b == 0) {x1 = a; y1 = 0; return;}
	exgcd(b, a % b);
	ll x2 = x1, y2 = y1;
	x1 = y2; y1 = x2 - (a / b) * y2;
}

ll getni(ll x, ll p) {
	if(gcd(x, p) != 1 && gcd(x, p) != -1) return inf;
	exgcd(x, -p);
	return (x1 % p + p) % p;
}

ll lcm, mo;

ll mul(ll x, ll y, const ll mo) {
	x %= mo; y %= mo;
    ll z = (long double) x * y / mo; z = x * y - z * mo;
    if(z < 0) z += mo; else if(z > mo) z -= mo;
    return z;
}

ll solve(ll a, ll b, ll c) {
	ll d = gcd(a, gcd(b, c));
	a /= d; b /= d; c /= d;
	if(c == 0) return b;
	if(gcd(a, b) != 1 && gcd(a, b) != -1) return inf;
	exgcd(a, b);
	return mul(x1, c, mo);	
}


int main() {
	for(scanf("%d", &T); T; T --) {
		scanf("%d %d", &n, &m);
		fo(i, 1, n) scanf("%lld", &a[i]);
		fo(i, 1, n) scanf("%lld", &p[i]);
		fo(i, 1, n) scanf("%lld", &v2[i]);
		fo(i, 1, m) scanf("%lld", &v1[i]);
		
		s.clear();
		fo(i, 1, m) s.insert(v1[i]);
		mx = 0; ans = 0; q = 0;
		
		fo(i, 1, n) {
			ll x;
			if((*s.begin()) >= a[i]) {
				x = *s.begin();
			} else {
				if((*s.rbegin()) > a[i]) {
					x = *(-- s.upper_bound(a[i]));
				} else x = *s.rbegin();
			}
			s.erase(s.find(x)); s.insert(v2[i]);
			ll d = gcd(x, gcd(a[i], p[i]));
			x /= d; a[i] /= d; p[i] /= d;
			mx = max(mx, a[i] / x + (a[i] % x > 0));
			if(p[i] == 1) continue;
			mo = p[i];
			ll y = solve(x, -p[i], a[i]);
			if(y == inf) {ans = -1; break;}
			y = (y % p[i] + p[i]) % p[i];
			b[++ q].a = y; b[q].p = p[i];
		}
		if(ans == -1) {
			printf("-1\n"); continue;
		}
		fo(i, 2, q) {
			ll d = gcd(b[i - 1].p, b[i].p);
			lcm = b[i - 1].p / d * b[i].p;
			mo = lcm;
			ll x = solve(b[i - 1].p, -b[i].p, b[i - 1].a - b[i].a);
			if(x == inf) {
				ans = -1; break;
			}
			x = b[i - 1].a - mul(x, b[i - 1].p, lcm);
			x = (x % lcm + lcm) % lcm;
			b[i].p = lcm; b[i].a = x;
		}
		if(ans == -1) {
			printf("-1\n"); continue;
		}
		if(q == 0) {
			ans = mx;			
		} else {
			ans = mx / b[q].p * b[q].p + b[q].a;
			if(ans < mx) ans += b[q].p;
		}
		printf("%lld\n", ans);
	}
}

评测结果