1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
| #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/trie_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/priority_queue.hpp>
using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; typedef long long ll;
const int N = 200005; int n, m, k; ll t[N], sword[N];
ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ll gcd = exgcd(b, a % b, x, y); ll t = x; x = y; y = t - a / b * y; return gcd; }
ll excrt(vector<ll> &a, vector<ll> &b, vector<ll> &p) { assert(a.size() == b.size() && a.size() == p.size()); ll A = 0, P = 1; for (int i = 0; i < a.size(); i++) { ll x, y; ll p1 = P, p2 = p[i]; ll a1 = A, a2 = a[i]; ll b1 = 1, b2 = b[i]; ll m1 = p1 * b2, m2 = p2 * b1; ll d = exgcd(m1, m2, x, y); if ((-a1 * b2 + a2 * b1) % d)return -1; ll lcm = p[i] / d * P; __int128 k1 = ((__int128) -a1 * b2 + a2 * b1) / d % lcm * x % lcm; A = (a1 + k1 * p1) % lcm; P = lcm; } A = (A % P + P) % P; for (int i = 0; i < a.size(); i++) { ll now = (a[i] + b[i] - 1) / b[i]; if (A < now) A += (now - A + P - 1) / P * P; } return A; }
int main() { int p, q, u, v, w, x, y, z, T; cin >> T; while (T--) { scanf("%d%d", &n, &m); vector<ll> a(n), b(n), p(n); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); for (int i = 0; i < n; i++) scanf("%lld", &p[i]); for (int i = 0; i < n; i++) scanf("%lld", &t[i]); multiset<ll> st; for (int i = 0; i < m; i++) scanf("%lld", &sword[i]), st.insert(sword[i]); for (int i = 0; i < n; i++) { auto p = st.upper_bound(a[i]); if (p == st.begin()) b[i] = *p; else b[i] = *--p; st.erase(p); st.insert(t[i]); } printf("%lld\n", excrt(a, b, p)); } return 0; }
|