「NOI2018」屠龙勇士题解

2020-02-27

NOI 又不怎么考数论题.

from 某神仙

题目链接: https://www.luogu.com.cn/problem/P4774

~~最近好颓啊 = =, 写题又不想自己写, 学东西又不能静下来好好学~~

这是一道拓展中国剩余定理的模板题, 由此发现之前学的 Ex CRT 很假, 所以来整理一下.

这还是一道阅读理解题 = =.

前置知识

基础数论
拓展中国剩余定理

题目思路

记对第 $i$ 个巨龙使用剑的攻击力为 $A_i$.

容易发现, $A_i$ 的值其实很好确定, 直接在 multiset 上二分即可. 那么, 现在的问题为

给定 $a_i, A_i, p_i$, 有

$\begin{equation} \left \{ \begin{array}{ccc} a_1 - A_1 x &\equiv & 0 \pmod {p_1} \\ a_2 - A_2 x &\equiv & 0 \pmod {p_2} \\ &\vdots& \\ a_n - A_n x &\equiv & 0 \pmod {p_n} \end{array} \right. \end{equation}$

求满足条件的最小 $x$, 其中 $p_i$ 不一定为互质.

其实这只是一个 Ex CRT, 把式子稍微转换一下, 得

$x \equiv a_i \cdot A_i^{-1} \pmod {p_i}$

这就和模板题完全一样了, 注意到 $p_i$ 并不是质数, 求乘法逆元的时候跑 exgcd 就好了. 另外会出现无解的情况, 在下文会细谈.

现在问题已经解决了大半, 但是有一些特判不能忽略.

首先考虑无解. 一番分析之后可以发现, 无解有两种情况:

化简同余式时无解

考虑化简的过程, 我们把 $A_i x \equiv a_i \pmod {p_i}$ 化成不定方程的形式, 即
$A_i x + y p_i = a_i$
根据裴蜀定理, 该方程有解需要满足 $\gcd(A_i, p_i) \mid a_i$, 否则无解.

虽然无解的情况已经解决了, 不妨顺水推舟, 把化简的过程写完.

记 $g = \gcd(A_i, p_i)$, 于是两边同除 $g$, 有
$\frac{A_i}{g} x + \frac{p_i}{g} y = \frac{a_i}{g}$
记 $A_i^{-1}$ 为模 $p_i$ 意义下的逆元, 整理, 得
$x \equiv \frac{a_i}{g}\cdot A_i^{-1}\pmod{ \frac{p_i}{g} }$
合并同余式时无解

考虑两同余式转换为不定方程后相减, 和上一情况同理.

其次考虑题目的特殊性质.

特性 2 没什么好说的, 和文末提示 “你所用到的中间结果可能很大，注意保存中间结果的变量类型” 一样, 要注意每个同余方程模数的数量级都在 $10^{12}$, 建议使用 long long 以及龟速乘.

考虑特性 1 的反例, 也就是 $a_i > p_i$, 会对以上的过程产生什么影响.

如果存在一个 $x$, 满足 $A_i x = a_i - p_i$, 依然满足 $A_i x \equiv a_i \pmod {p_i}$, 但显然不满足题意 = =

幸运的是, 不满足特性 1 的数据点另外满足 $p_i = 1$, 此时答案就是

$\max _{i = 1} ^n \{\ \lceil \dfrac{a_i}{A_i} \rceil\ \}$

~~放到题目背景里就是一直砍, 一直砍~~

那么这道题就做完了 = =.

比较良心的是, 大样例 (from loj) 存在部分数据满足这几个特殊性质.

作为 Day2 T1 (应该? ) 算是送温暖吧, 但对于我这种背板选手一发 15 pts 还是算了 = =.

代码实现

// Luogu P4774
// DeP
#include <set>
#include <cctype>
#include <cstdio>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
typedef multiset<LL>::iterator IT;
// 准备迎接 CCF 的省选了 = =
const int MAXN = 1e5+5;

inline LL smul(LL base, LL b, LL m) {
    LL ret = 0;
    while (b > 0) {
        if (b & 1) ret = (ret + base) % m;
        base = (base + base) % m, b >>= 1;
    }
    return ret;
}

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

int n, m;
multiset<LL> S;
LL A[MAXN], a[MAXN], p[MAXN], w[MAXN];

LL solve() {
    // pre done
    for (int i = 1; i <= n; ++i) {
        static LL x, d, y;
        exgcd(A[i], p[i], d, x, y);
        if (a[i] % d != 0) return -1;
        p[i] /= d;
        A[i] = smul(a[i] / d, (x % p[i] + p[i]) % p[i], p[i]);
    }
    // extra CRT
    LL ret = A[1], M = p[1];
    for (int i = 2; i <= n; ++i) {
        static LL x, y, c, d, mod;
        c = ((A[i] - ret) % p[i] + p[i]) % p[i];
        exgcd(M, p[i], d, x, y);
        if (c % d != 0) return -1;
        mod = p[i] / d, x = smul(x, c / d, mod);
        ret += x * M, M *= mod, ret = (ret % M + M) % M;
    }
    return ret;
}

LL p1solve() {
    LL ret = 0;
    for (int i = 1; i <= n; ++i)
        ret = max(ret, (a[i] + A[i] - 1) / A[i]);
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti; read(Ti);
    while (Ti--) {
        // init
        S.clear();
        bool p1 = true;
        // input
        read(n), read(m);
        for (int i = 1; i <= n; ++i) read(a[i]);
        for (int i = 1; i <= n; ++i) read(p[i]), p1 &= p[i] == 1;
        for (int i = 1; i <= n; ++i) read(w[i]);
        for (int x, i = 1; i <= m; ++i) read(x), S.insert(x);
        // pre done
        for (int i = 1; i <= n; ++i) {
            IT ite = (a[i] < *S.begin())? S.begin(): (--S.upper_bound(a[i]));
            A[i] = *ite;
            S.erase(ite), S.insert(w[i]);
        }
        // output
        printf("%lld\n", p1? p1solve(): solve());
    }
    return 0;
}

DepletedPrism's Blog

「NOI2018」屠龙勇士 题解

前置知识

题目思路

代码实现

「NOI2018」屠龙勇士题解