代码

#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <algorithm>
#include <map>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

const int N = 100010;

int n, m;
int ex[N], bat[N];
ll a[N], p[N];

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll exGcd(ll a, ll b, ll& x, ll& y);
ll mul(ll a, ll b, ll p);
ll inv(ll a, ll p);

int main() {
	int t;
	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("%d", &ex[i]);
		map<int, int> sw;
		for (int i = 1; i <= m; ++i) {
			int s;
			scanf("%d", &s);
			++sw[s];
		}

		for (int i = 1; i <= n; ++i) {
			map<int, int>::iterator it = sw.begin();
			if (a[i] >= it->first) {
				it = sw.end();
				--it;
				if (a[i] < it->first) {
					it = sw.upper_bound((int) a[i]);
					--it;
				}
			}
			bat[i] = it->first;
			if (--it->second == 0)
				sw.erase(it);
			++sw[ex[i]];
		}
		ll lcm = 1, x = 0;
		for (int i = 1; i <= n; ++i) {
			ll xx, yy;
			ll g = exGcd(bat[i], p[i], xx, yy);
			if (xx < 0)
				xx += p[i];
			if (a[i] % g != 0) {
				x = -1;
				break;
			}
			ll fc = mul(a[i] / g, xx, p[i] /= g);
			g = gcd(lcm, p[i]);
			if (x % g != fc % g) {
				x = -1;
				break;
			}
			ll rem = x % g;
			ll x1 = x / g, x2 = fc / g, p1 = lcm / g, p2 = p[i] / g;
			lcm = p1 * p2;
			ll q2 = mul(inv(p1, p2), p1, lcm), q1 = mul(inv(p2, p1), p2, lcm);
			x = mul(x1, q1, lcm) + mul(x2, q2, lcm);
			if (x >= lcm)
				x -= lcm;
			x = x * g + rem;
			lcm *= g;
		}
		if (x == -1) {
			puts("-1");
			continue;
		}
		for (int i = 1; i <= n; ++i) {
			if (x * bat[i] < a[i]) {
				ll delt = a[i] - bat[i] * x;
				x += (delt + lcm * bat[i] - 1) / (lcm * bat[i]);
			}
		}
		printf("%lld\n", x);
	}
	return 0;
}

ll inv(ll a, ll p) {
	ll x, y;
	exGcd(a, p, x, y);
	if (x < 0)
		x += p;
	return x;
}

ll mul(ll a, ll b, ll p) {
	a %= p;
	b %= p;
	if (a > b)
		swap(a, b);
	ll ret = 0;
	while (a) {
		if (a & 1) {
			ret += b;
			if (ret >= p)
				ret -= p;
		}
		b += b;
		if (b >= p)
			b -= p;
		a >>= 1;
	}
	return ret;
}

ll exGcd(ll a, ll b, ll& x, ll& y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	ll ret = exGcd(b, a % b, y, x);
	y -= a / b * x;
	return ret;
}

评测结果