题解 P4774 【[NOI2018]屠龙勇士】

· · 题解

背景

感觉这题还是比较清晰的。

思路

Part I

很明显每条龙对应的剑是确定的，用平衡树处理出第 i 条龙对应的剑的攻击力是 b_i，为了方便展示，我就偷懒用 multiset<long long> 实现了。

那么现在题意就转化为，对同余方程组

\begin{cases}b_1x\equiv a_1\pmod {p_1}\\b_2x\equiv a_2\pmod {p_2}\\\qquad\cdots\\b_nx\equiv a_n\pmod {p_n}\end{cases}

求最小非负整数解。

需要注意的是，要保证可以把龙血砍成负的，即 x 不能小于将每条龙砍成负血的最小刀数。

Part II

在此之前，不妨先想想普通的扩展中国剩余定理是怎么做的，即所有 b_i=1 的情况。

  1. 假设已经得到了前 i-1 组同余方程的解，记为 ans；
  2. 设 M=\operatorname{lcm}(p_1,p_2,\ldots,p_{i-1})，则对于任意的整数 x，ans+Mx 是前 i-1 组同余方程的通解；
  3. 我们想得到前 i 组同余方程的解，就是想找到一个 x，满足 ans+Mx\equiv a_i\pmod {p_i}；
  4. 移项得 Mx\equiv a_i-ans\pmod{p_i}；
  5. 这类式子一看就是老扩欧了，转化成 Ax+By=C 的形式用扩展欧几里得求解，即：
(M)x+(p_i)y=(a_i-ans)

Part III

那么有系数 b_i 怎么搞呢？逆元是不可能逆元的，又不互质，在模 p_i 意义下 b_i 未必有逆元。

害，其实还是换汤不换药呗。

  1. 假设已经得到了前 i-1 组同余方程的解，记为 ans；
  2. 设 M=\operatorname{lcm}(p_1,p_2,\ldots,p_{i-1})，则对于任意的整数 x，ans+Mx 是前 i-1 组同余方程的通解；
  3. 想得到前 i 组同余方程的解，就是想找到一个 x，满足 b_i(ans+Mx)\equiv a_i\pmod {p_i}；
  4. 移项得 b_iMx\equiv a_i-b_ians\pmod{p_i}；
  5. 这类式子一看就是老扩欧了，转化成 Ax+By=C 的形式用扩展欧几里得求解，即：
(b_iM)x+(p_i)y=(a_i-b_ians)

Part IV

几点注意事项：

  1. 判无解就跟平常扩欧的判解一样，若 C 不是 \gcd(A,B) 的倍数，则无解，即若 a_i-b_ians 不是 \gcd(b_iM,p_i) 的倍数，则无解；
  2. 看下数据范围，明显有两处需要龟速乘的，鉴于大家都会，我就偷懒用 __int128 实现了。

代码

#include <set>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 100005;
int T, n, m, b[maxn], t[maxn];
long long a[maxn], p[maxn], mx;
multiset<long long> s;
void exgcd(long long A, long long B, long long &x, long long &y, long long &gcd) {
    if(!B) x = 1, y = 0, gcd = A;
    else exgcd(B, A%B, y, x, gcd), y -= (A/B) * x;
}
long long ExCRT() {
    long long ans = 0, lcm = 1, x, y, gcd, A, B, C;
    for(int i = 1; i <= n; ++i) {
        A = (__int128)b[i] * lcm % p[i];
        B = p[i];
        C = (a[i]-b[i]*ans%p[i]+p[i]) % p[i];
        exgcd(A, B, x, y, gcd), x = (x%B+B) % B;
        if(C % gcd) return -1;
        ans += (__int128)(C/gcd) * x % (B/gcd) * lcm % (lcm*=B/gcd);
        ans %= lcm;
    }
    if(ans < mx) ans += ((mx-ans-1)/lcm+1) * lcm;
    return ans;
}
int main() {
    scanf("%d", &T);
    while(T--) {
        s.clear(), mx = 0;
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
        for(int i = 1; i <= n; ++i) scanf("%lld", &p[i]);
        for(int i = 1; i <= n; ++i) scanf("%d", &t[i]);
        for(int i = 1, x; i <= m; ++i) scanf("%d", &x), s.insert(x);
        for(int i = 1; i <= n; ++i) {
            auto u = s.upper_bound(a[i]);
            if(u != s.begin()) u--;
            b[i] = *u, s.erase(u), s.insert(t[i]);
            mx = max(mx, (a[i]-1)/b[i]+1);
        }
        printf("%lld\n", ExCRT());
    }
}

P.S.

其实 emptyset 不懒，只是这样比较方便在题解区展示啦。

emptyset 自己 yy 的做法，有 hack 数据可以叫她（有点担心溢出的问题）。

觉得还不错的话点个赞吧。