屠龙勇士

发表于 | 更新于
本文字数： 4.4k | 阅读时长 ≈ 4 分钟

$Dragon$

$Description$

$Ps:$

一道好题。

重点在于对同余方程的推导，然后就很裸了。

对 $multiset$ 的应用也很漂亮。

$Solution$

首先，我们根据题目所给条件，可以得出一个方程：
$$
x_i \times Atk_i \equiv a_i \pmod {p_i}
$$
也即
$$
x_i \equiv a_i \times Atk_{i}^{-1} \pmod {p_i}
$$
然后考虑如何求出 $Atk_{i}^{-1}$ ，并将其变成扩展 $Crt$ 的形式。

由于 $Atk_i$ 与 $p_i$ 不互素，所以无法直接求出他的逆元，所以我们考虑先求出 $gcd(a_i, p_i, Atk_i)$ ，然后把三个同除以 $gcd$ 。注意如果此时如果两数仍不互素，就无解。

然后 $exgcd$ 求下逆元，就变成拓展 $Crt$ 板子了。

$Code:$

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
//#include<tr1/unordered_map>
//#include"Bignum/bignum.h"
//#define lll bignum
#define ls(x) ( x << 1 )
#define rs(x) ( x << 1 | 1 )
//#define mid ( ( l + r ) >> 1 )
#define lowbit(x) ( x & -x )
#define It multiset<ll>::iterator
#define debug(x) (cout << "#x = " << x << endl)
#define re register
#define For(i, j, k) for(re int i = (j); i <= (k); i++)
#define foR(i, j, k) for(re int i = (j); i >= (k); i--)
#define Cross(i, j, k) for(re int i = (j); i; i = (k))
using namespace std;
typedef long long ll;
const ll N = 100011;
const ll inf = 0x3f3f3f3f3f3f;

multiset < ll > Atk;

ll T, n, m, mx = 0, a[N], p[N], Blade[N], GetAtk[N];

namespace IO {

    #define dd ch = getchar()
    inline ll read() {
        ll x = 0; bool f = 0; char dd;
        for (; !isdigit (ch); dd) f ^= (ch == '-');
        for (; isdigit (ch); dd)  x = (x << 3) + (x << 1) + (ch ^ 48);
        return f? -x: x;
    }
    #undef dd

    inline void write( ll x ) {
        if ( x < 0 ) putchar ( '-' ), x = -x;
        if ( x > 9 ) write ( x / 10 );
        putchar ( x % 10 | 48 );
    }

    inline void wrn ( ll x ) { write (x); putchar ( ' ' ); }

    inline void wln ( ll x ) { write (x); putchar ( '\n' ); }

    inline void wlnn ( ll x, ll y ) { wrn (x), wln (y); }

}

using namespace IO;

ll mul ( ll a, ll b, ll p ) {
    ll L = a * (b >> 25ll) % p * (1ll << 25) % p;
    ll R = a * (b & ((1ll << 25) - 1)) % p;
    return (L + R) % p;
}

//inline ll mul ( ll a, ll b, ll p ) {
//    a %= p, b %= p;
//    return ( (a * b - (ll)((long double)(a * b - 0.5) / p) * p) % p + p ) % p;
////    ll res = 0;
////    for (; b; b >>= 1, a = (a + a) % p) res = (b & 1)? Add (res, a, p): res;
////    return res;
//}

inline ll gcd ( ll a, ll b ) { return !b? a: gcd (b, a % b); }

inline void exgcd ( ll a, ll b, ll &d, ll &x, ll &y ) {
    if (b) exgcd ( b, a % b, d, y, x ), y -= a / b * x;
    else d = a, x = 1, y = 0; return ;
}

inline ll Inv ( ll a, ll b ) {
    ll d, x, y;
    exgcd (a, b, d, x, y);
    return x + b > b? x: x + b;
}

inline ll exCrt( ll A[], ll B[], ll M[], ll &res ) {
    res = 0; ll lcm = 1;
    For ( i, 1, n ) {
        ll a = mul (A[i], lcm, M[i]), 
            b = B[i] - mul (A[i], res, M[i]), d = gcd (a, M[i]);
        if (b % d) return res = -1, 0;
        ll x = mul (b / d, Inv (a / d, M[i] / d), M[i] / d);
        res += lcm * x, lcm *= M[i] / d;
    } return res = (res % lcm + lcm) % lcm, lcm;
}

int main() {
  freopen("dragon.in", "r", stdin);
  freopen("dragon.out", "w", stdout);
    T = read(); while ( T-- ) {
        Atk.clear(); mx = 0;
        n = read(), m = read();
        For ( i, 1, n ) a[i] = read();
        For ( i, 1, n ) p[i] = read();
        For ( i, 1, n ) GetAtk[i] = read();
        For ( i, 1, m ) Atk.insert(read());
        For ( i, 1, n ) {
            It it = Atk.upper_bound(a[i]); 
                // 找第一把大于初始生命值的。 
            if ( it != Atk.begin() ) --it; 
            /* 
                如果不是攻击力最低的一把，就减一，选不高于巨龙生命值的
                武器中攻击最高的。 
            */
            Blade[i] = (*it); // 当前所用的剑。 
            Atk.erase(it), Atk.insert(GetAtk[i]); // 换上杀死后的剑。
            mx = max ( mx, (a[i] + Blade[i] - 1) / Blade[i] ); 
                // 即最少砍几刀杀死一头龙中最多需要砍的次数。
        }
        ll x, lcm = exCrt (Blade, a, p, x);
        if ( x != -1 && x < mx ) 
            x += lcm * ( (mx - x + lcm - 1) / lcm ); // 向上取整。 
        wln (x);
    } return 0;
}

/*
2
3 3
3 5 7
4 6 10
7 3 9
1 9 1000
3 2
3 5 6
4 8 7
1 1 1
1 1

59
-1
*/

[题目链接](