屠龙勇士

$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:$

复制

#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
*/

[题目链接](