题意

某游戏要按顺序杀掉 n 条巨龙,巨龙初始生命为 a_i。每打一条龙从剑的集合 A 里面选出一把攻击力为 A_i 的剑,满足 A_ia_i 的前驱,否则则是最小的。选完剑之后打龙,攻击 x 次,然后巨龙连续使用恢复能力,每次恢复 p_i 血量,若在某次恢复后或在攻击结束后巨龙生命值为 0,则通过本关,剑消失,并被给予一把新剑。

求最小的 x,无解 -1

思路

对于每次攻击的龙取的剑,使用 multiset 维护即可,每次 upper_bound 查找,如果没有返回 sword.begin() 就将迭代器自减。

void init()
{
    minx = 0;
    sword.clear();
    N = read(), M = read();
    FOR(i, 1, N)
        a[i] = read();
    FOR(i, 1, N)
        p[i] = read();
    FOR(i, 1, N)
        A1[i] = read();
    FOR(i, 1, M)
        sword.insert(read());
    FOR(i, 1, N)
    {
        multiset<ll>::iterator it = sword.upper_bound(a[i]);
        if (it != sword.begin())
            --it;
        A[i] = *it;
        minx = max(minx, a[i] % A[i] == 0 ? a[i] / A[i] : a[i] / A[i] + 1);//等下解释
        sword.erase(it);
        sword.insert(A1[i]);
    }
    return;
}

然后,问题就变成了求满足

\begin{cases}
A_1 x\equiv a_1\pmod{p_1}\
\cdots\
A_n x\equiv a_n\pmod{p_n}
\end{cases}

的最小正整数 x。乍一看这东西很像 exCRT 的形式,但是发现 x 前面带有系数,所以考虑 exCRT 的思维方式:设前 i-1 个方程的一个解为 \text{ans},模数的最小公倍数为 \text{lcm},则不难发现前 i-1 个方程的通解为 \text{ans} + x\cdot\text{lcm},x\in\mathbb{Z}。带入第 i 个方程,有

A_i(\text{ans} + x\cdot\text{lcm})\equiv a_i\pmod{p_i}

引入一个新变量 y,将上述方程化为不定方程形式:

A_i\cdot\text{lcm}\cdot x+p_iy=a_i – A_i\text{ans}

先用 exgcd 求出

A_i\cdot\text{lcm}\cdot x’+p_iy’=\gcd(A_i\cdot\text{lcm},p_i)

的一组特解 x’,y’,然后判无解,显然当 \gcd(A_i\cdot\text{lcm},p_i)\not| a_i – A_i\text{ans} 时整个方程组无解,否则 \displaystyle x = x’\cdot \frac{A_i\cdot\text{lcm}}{\gcd(A_i\cdot\text{lcm},p_i)},y = y’\cdot\frac{p_i}{\gcd(A_i\cdot\text{lcm},p_i)}

所以前 i 个方程合并后的解 \text{ans}’ = \text{ans} + x\cdot \text{lcm},模数的最小公倍数 \text{lcm}’ = \text{lcm}\cdot p_i/\gcd

一直合并即可。

但是事情没有完。

注意:如果刀的刀数不够多,有可能龙剩下的血量是正的但其模 p_i 仍等于 0,所以我们求的并不是最小正整数解,是最小满足条件的正整数解。至少要刀的刀数可以一开始算出来,最后如果发现刀数不够的话按照倍数来补刀就行了。

注意快速乘,取模,负数的处理

#include <cstdio>
#include <cctype>
#include <set>
#define FOR(i, a, b) for (R int i = a; i <= b; ++i)
#define il inline
#define R register

const int maxn = 1e5 + 5;
using std::multiset;
typedef long long ll;

inline ll read()
{
    char c = getchar();
    ll s = 0;
    bool x = 0;
    while (!isdigit(c))
        x = x | (c == '-'), c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x?-s:s;
}

template<typename T> inline T max(T a, T b) {return a > b ? a : b;}

multiset<ll> sword;
ll N, M;
ll a[maxn], p[maxn], A1[maxn], A[maxn];
ll r[maxn], m[maxn], minx;

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

ll mul(ll a, ll b, ll mod)
{
    ll ans = 0, x = a;
    b = (b + mod) % mod, a = (a + mod) % mod;
    for (; b; b >>= 1ll)
    {
        if (b & 1ll)
            ans = (ans + x) % mod;
        x = (x << 1) % mod;
    }
    return ans;
}

void init()
{
    minx = 0;
    sword.clear();
    N = read(), M = read();
    FOR(i, 1, N)
        a[i] = read();
    FOR(i, 1, N)
        p[i] = read();
    FOR(i, 1, N)
        A1[i] = read();
    FOR(i, 1, M)
        sword.insert(read());
    FOR(i, 1, N)
    {
        multiset<ll>::iterator it = sword.upper_bound(a[i]);
        if (it != sword.begin())
            --it;
        A[i] = *it;
        minx = max(minx, a[i] % A[i] == 0 ? a[i] / A[i] : a[i] / A[i] + 1);
        sword.erase(it);
        sword.insert(A1[i]);
    }
    return;
}

ll exCRT()
{
    ll lcm = 1, ans = 0, x, y, k1, k2, k3, gcd;
    FOR(i, 1, N)
    {
        k1 = mul(A[i], lcm, p[i]), k2 = p[i], k3 = ((a[i] - mul(A[i], ans, p[i])) % p[i] + p[i]) % p[i];
        gcd = exgcd(k1, k2, x, y);
        x = (x % p[i] + p[i]) % p[i];
        if (k3 % gcd)
            return -1;
        ans += mul(x, k3 / gcd, p[i] / gcd) * lcm;
        lcm = lcm * (p[i] / gcd);
    }
    if (ans < minx)
    {
        ll tmp = (minx - ans) % lcm == 0 ? (minx - ans) / lcm : (minx - ans) / lcm + 1;
        ans = ans + tmp * lcm;
    }
    return ans;
}

int main()
{
    int T = read();
    while (T--)
    {
        init();
        printf("%lld\n", exCRT());
    }
    return 0;
}
最后修改日期:2020年12月31日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。