题目描述

[NOI2018] 屠龙勇士

题目描述

小 D 最近在网上发现了一款小游戏。游戏的规则如下：

• 游戏的目标是按照编号 $1 \rightarrow n$ 顺序杀掉 $n$ 条巨龙，每条巨龙拥有一个初始的生命值 $a_i$ 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 $p_i$ ，直至生命值非负。只有在攻击结束后且当生命值 恰好 为 $0$ 时它才会死去。
• 游戏开始时玩家拥有 $m$ 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。

小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格，于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：

• 每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择 攻击力最低 的一把剑作为武器。
• 机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 $x$ 次，使巨龙的生命值减少 $x \times ATK$ 。
• 之后，巨龙会不断使用恢复能力，每次恢复 $p_i$ 生命值。若在使用恢复能力前或某一次恢复后其生命值为 $0$ ，则巨龙死亡，玩家通过本关。

那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数 $x$ 设置为多少，才能用最少的攻击次数通关游戏吗？

当然如果无论设置成多少都无法通关游戏，输出 $-1$ 即可。

输入格式

第一行一个整数 $T$，代表数据组数。

接下来 $T$ 组数据，每组数据包含 $5$ 行。

• 每组数据的第一行包含两个整数，$n$ 和 $m$ ，代表巨龙的数量和初始剑的数量；
• 接下来一行包含 $n$ 个正整数，第 $i$ 个数表示第 $i$ 条巨龙的初始生命值 $a_i$；
• 接下来一行包含 $n$ 个正整数，第 $i$ 个数表示第 $i$ 条巨龙的恢复能力 $p_i$；
• 接下来一行包含 $n$ 个正整数，第 $i$ 个数表示杀死第 $i$ 条巨龙后奖励的剑的攻击力；
• 接下来一行包含 $m$ 个正整数，表示初始拥有的 $m$ 把剑的攻击力。

输出格式

一共 $T$ 行。

第 $i$ 行一个整数，表示对于第 $i$ 组数据，能够使得机器人通关游戏的最小攻击次数 $x$ ，如果答案不存在，输出 $-1$。

样例 #1

样例输入 #1

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

样例输出 #1

59
-1

提示

更多样例

更多样例请在附加文件中下载。

样例 2

见附加文件中的 dragon2.in 与 dragon2.ans。

样例 1 解释

第一组数据：
- 开始时拥有的剑的攻击力为 $\{1,9,10\}$，第 $1$ 条龙生命值为 $3$，故选择攻击力为 $1$ 的剑，攻击 $59$ 次，造成 $59$ 点伤害，此时龙的生命值为 $-56$，恢复 14 次后生命值恰好为 $0$，死亡。

• 攻击力为 $1$ 的剑消失，拾取一把攻击力为 $7$ 的剑，此时拥有的剑的攻击力为
  $\{7,9,10\}$，第 2 条龙生命值为 $5$，故选择攻击力为 $7$ 的剑，攻击 $59$ 次，造成 $413$ 点伤害，此时龙的生命值为 $-408$，恢复 $68$ 次后生命值恰好为 $0$，死亡。

• 此时拥有的剑的攻击力为 $\{3,9,10\}$，第 $3$ 条龙生命值为 $7$，故选择攻击力为 $3$ 的剑，攻击 $59$ 次，造成 $177$ 点伤害，此时龙的生命值为 $-170$，恢复 $17$ 次后生命值恰好为 0，死亡。

• 没有比 $59$ 次更少的通关方法，故答案为 $59$。

第二组数据：
不存在既能杀死第一条龙又能杀死第二条龙的方法，故无法通关，输出 $-1$。

子任务

特性 1 是指：对于任意的 $i$，$a_i \le p_i$。

特性 2 是指：$\operatorname{lcm}(p_i) \le 10^6$，即所有 $p_i$ 的 最小公倍数 不大于 $10^6$。

对于所有的测试点，$T \le 5$，所有武器的攻击力 $\le 10^6$，所有 $p_i$ 的最小公倍数 $\le 10^{12}$。

保证 $ T, n, m $ 均为正整数。

提示

你所用到的中间结果可能很大，注意保存中间结果的变量类型。

算法1

(exCRT) $O(T*nlog(n))$

Part I

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

那么现在题意就转化为，对同余方程组
$ \begin{cases} b_1 x \equiv a_1 \pmod{p_1} \\ b_2 x \equiv a_2 \pmod{p_2} \\ \vdots \\ b_n x \equiv a_n \pmod{p_n} \end{cases} $
求最小非负整数解。

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

Part II

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

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

Part III

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

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

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

Part IV

几点注意事项：

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

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=1e5+10;
int n,m;
LL a[N],p[N],b[N],c[N];
LL mx;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    LL d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
LL exCRT()
{
    LL ans=0,lcm=1,x,y,d,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];
        d=exgcd(A,B,x,y),x=(x%B+B)%B;
        if(C%d)return -1;
        ans+=(__int128)(C/d)*x%(B/d)*lcm%(lcm*=B/d);
        ans%=lcm;
    }
    if(ans<mx)ans+=((mx-ans+lcm-1)/lcm)*lcm;
    return ans;   
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        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("%lld",&c[i]);
        multiset<LL> S;
        mx=0;
        for(int i=1;i<=m;i++)
        {
            LL x;
            scanf("%lld",&x);
            S.insert(x);
        }
        for(int i=1;i<=n;i++)
        {
            auto it=S.upper_bound(a[i]);
            if(it!=S.begin())it--;
            b[i]=*it;
            S.erase(it);
            S.insert(c[i]);
            mx=max(mx,(a[i]+b[i]-1)/b[i]);
        }
        printf("%lld\n",exCRT());
    }
    return 0;
}