Pedestrian1's BLOG
0%

NOI2018 屠龙勇士

发表于 更新于

题目所求即为对所有有

考虑以下同余方程的合并

令

则

设

则通解，，可通过求解

，注意此处不需要乘上系数

最初添加一个方程即可做到

此时可求出满足同余方程的答案，对于条件扫一遍处理即可 

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;
//tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> tr;
//__gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> qu;
//typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
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;
}