洛谷 P4774 / loj 2721 [NOI2018] 屠龙勇士 题解【同余】【exgcd】【exCRT】

点击量：200

推导过程存在漏洞+exCRT板子没打熟于是期望得分÷实际得分=∞？

目录

题目描述

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

• 游戏的目标是按照编号 $ 1\sim n$ 顺序杀掉 $ n$ 条巨龙，每条巨龙拥有一个初始的生命值 $ a_i$。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 $ p_i$，直至生命值非负。只有在攻击结束后且当生命值恰好为 $ 0$ 时它才会死去。

• 游戏开始时玩家拥有 $ m$ 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。

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

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

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

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

输入格式

从文件 dragon.in 中读入数据。

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

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

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

输出格式

输出到文件 dragon.out 中。

一共 $ T$ 行。

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

样例输出

59
-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。

子任务

测试点编号	$ n$	$ m$	$ p_i$	$ a_i$	攻击力	其他限制
$ 1$	$ \le 10^5$	$ =1$	$ =1$	$ \le 10^5$	$ =1$	无
$ 2$
$ 3$					$ \le 10^5$
$ 4$
$ 5$	$ \le 10^3$	$ \le 10^3$	$ \le 10^5$			特性 $ 1$、 特性 $ 2$
$ 6$
$ 7$
$ 8$	$ =1$	$ =1$	$ \le 10^8$	$ \le 10^8$	$ \le 10^6$	特性 $ 1$
$ 9$
$ 10$
$ 11$
$ 12$
$ 13$
$ 14$	$ =10^5$	$ =10^5$	$ =1$			无特殊限制
$ 15$
$ 16$	$ \le 10^5$	$ \le 10^5$	所有 $ p_i$ 是质数	$ \le 10^{12}$		特性 $ 1$
$ 17$
$ 18$			无特殊限制
$ 19$
$ 20$

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

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

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

提示

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

题解：

整道题使用 exCRT 就能弄过去。

首先我们考虑每一轮用哪把剑砍龙。由于龙的顺序是固定的，所以每次剩下的剑的集合是固定的。但是每一轮都有剑在动态变化，因此我们用一棵平衡树来维护每次需要用的剑。

此时我们可以预处理砍每条龙用的是哪把剑，令砍第 $ i$ 条龙用的剑攻击力为 $ c_i$。

那么对于每把剑和相应的龙都应该存在一个 $ t\in\mathbb N$ ，使得
$$
a_i-c_ix+tp_i=0
$$
把它转化为同余方程的形式即为
$$
c_ix\equiv a_i\pmod{p_i}
$$
同时，我们要保证 $ x$ 取最小非负整数解时有意义，因此我们先用上面算出来的 $ c_i$ 分别求出每头龙至少需要砍多少下才会死，然后我们“提前”砍掉那么多。

即设变量 $ xmn$ 表示最少要砍的刀数
$$
xmn=\max_{1\le i\le n}\left\{\left\lceil\frac{a_i}{c_i}\right\rceil\right\}
$$
那么对于所有的 $ a_i$ 都要减去一个 $ xmn\times c_i$。

减过之后，对于所有的龙，我们把方程组列出来，有
$$
\left\{
\begin{aligned}
&c_1x\equiv a_1\pmod{p_1}\\
&c_2x\equiv a_2\pmod{p_2}\\
&\cdots\\
&c_nx\equiv a_n\pmod{p_n}
\end{aligned}
\right.
$$
变成了一个 CRT 的形式，由于 $ p_i$ 没有保证互质，所以我们使用 exCRT。

但是还有一点，我们用 CRT 解决问题时，左侧的 $ x$ 是没有系数的，我们要考虑怎么样把这边的系数化掉。

如果用逆元，两边同除 $ c_i$，那么只在 $ p_i$ 保证为质数的意义下才能成立，否则逆元无解导致题目答案错误。

我们可以用不定方程来推不定方程，因为 $ c_ix\equiv a_i$ 有一系列解，而且和 $ x$ 成线性关系，我们直接从这边转化过来就可以了。
$$
c_ix\equiv a_i\pmod{p_i}\\
c_ix+p_it=a_i,\ t\in \mathbb Z
$$
这里只有 $ x$ 和 $ t$ 是变量，因此只需要把 $ x$ 的特解和通解求出来，再构造一个形如 $ x\equiv b_i\pmod{d_i}$ 的方程就可以了。

对不定方程 $ c_ix+p_it=\gcd(c_i,p_i)$ 求解，得到 $ x=x_0$。等式两边同乘 $ \frac{a_i}{\gcd(c_i,p_i)}$，$ x=\frac{x_0a_i}{\gcd(c_i,p_i)}$。那么 $ \Delta x=\frac {p_i}{\gcd(c_i,p_i)}$。

由此构造出了新方程
$$
x\equiv \frac{x_0a_i}{\gcd(c_i,p_i)}\left(\bmod \frac{p_i}{\gcd(c_i,p_i)}\right)
$$
原方程组就变成了
$$
\left\{
\begin{aligned}
&x\equiv b_1\pmod{d_1}\\
&x\equiv b_2\pmod{d_2}\\
&\cdots\\
&x\equiv b_n\pmod{d_n}
\end{aligned}
\right.
$$
$ b_i,d_i$ 由上式计算。

然后套上 exCRT ，最后加上一开始算的 $ xmn$ 即可。

本来多简单一个题被我公式来公式去整这么复杂。

Code：

(平衡树(BST:: 部分)版面较大，multimap 可过)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define ll long long
namespace BST
{
int ls[200100],rs[200100],key[200100],rdm[200100],sz[200100],pcnt=0,root=0;
int Newnode(int x)
{
    ++pcnt;
    key[pcnt]=x;
    rdm[pcnt]=rand();
    ls[pcnt]=rs[pcnt]=0;
    sz[pcnt]=1;
    return pcnt;
}
void maintain(int rt)
{
    sz[rt]=sz[ls[rt]]+sz[rs[rt]]+1;
}
int Merge(int a,int b)
{
    if(!a||!b)
        return a|b;
    if(rdm[a]<rdm[b])
    {
        rs[a]=Merge(rs[a],b);
        maintain(a);
        return a;
    }
    ls[b]=Merge(a,ls[b]);
    maintain(b);
    return b;
}
void split(int rt,ll x,int &a,int &b)
{
    if(!rt)
    {
        a=b=0;
        return;
    }
    if(key[rt]<=x)//不高于
    {
        a=rt;
        split(rs[a],x,rs[a],b);
    }
    else
    {
        b=rt;
        split(ls[b],x,a,ls[b]);
    }
    maintain(rt);
}
void Insert(int x)
{
    int a,b;
    split(root,x,a,b);
    root=Merge(Merge(a,Newnode(x)),b);
}
void Delete(int x)
{
    int a,b,c;
    split(root,x-1,a,b);
    split(b,x,b,c);
    b=Merge(ls[b],rs[b]);
    root=Merge(Merge(a,b),c);
}
int getMin(int rt)
{
    if(ls[rt])
        return getMin(ls[rt]);
    return key[rt];
}
int getMax(int rt)
{
    if(rs[rt])
        return getMax(rs[rt]);
    return key[rt];
}
int getsword(ll x)
{
    int a,b,ans;
    split(root,x,a,b);
    if(!sz[a])
        ans=getMin(b);
    else
        ans=getMax(a);
    root=Merge(a,b);
    return ans;
}
}

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll g=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return g;
}
ll qmul(ll x,ll y,ll p)
{
    ll ans=0,f=1;
    if(x<0)
    {
        x=-x;
        f=-f;
    }
    if(y<0)
    {
        y=-y;
        f=-f;
    }
    while(y)
    {
        if(y&1)
            ans=(ans+x)%p;
        x=(x+x)%p;
        y>>=1;
    }
    return ans*f;
}
ll k[100100],a[100100],b[100100],c[100100];//k 指系数
//c 是奖励的
int main()
{
    freopen("dragon.in","r",stdin);
    freopen("dragon.out","w",stdout);
    int T,n,m;
    ll x,y;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        BST::pcnt=BST::root=0;
        for(int i=1;i<=n;++i)
            scanf("%lld",&a[i]);
        for(int i=1;i<=n;++i)
            scanf("%lld",&b[i]);
        for(int i=1;i<=n;++i)
            scanf("%lld",&c[i]);
        for(int i=1;i<=m;++i)
        {
            scanf("%lld",&x);
            BST::Insert(x);
        }
        ll xmn=0;
        for(int i=1;i<=n;++i)
        {
            ll f=BST::getsword(a[i]);
            BST::Delete(f);
            BST::Insert(c[i]);
            c[i]=f;
            xmn=xmn>ceil((double)a[i]/f)?xmn:ceil((double)a[i]/f);
        }
        for(int i=1;i<=n;++i)
            a[i]-=c[i]*xmn;

        bool flag=0;
        for(int i=1;i<=n;++i)
        {
            //c[i]*x=a[i](mod b[i])
            ll g=exgcd(c[i],b[i],x,y);
            if(a[i]%g)
            {
                puts("-1");
                flag=1;
                break;
            }
            ll t=b[i]/g;
            //特解 x
            x=(x%t+t)%t;
            x=qmul(x,a[i]/g,t);
            a[i]=x;
            b[i]/=g;//公差
            if(i==1)
                continue;
            g=exgcd(b[i],b[i-1],x,y);
            if((a[i]-a[i-1])%g)
            {
                puts("-1");
                flag=1;
                break;
            }
            t=b[i-1]/g;
            x=(x%t+t)%t;
            x=qmul(x,(a[i]-a[i-1])/g,t);
            a[i]-=qmul(b[i],x,b[i]/g*b[i-1]);
            b[i]=b[i]/g*b[i-1];
            a[i]=(a[i]%b[i]+b[i])%b[i];
        }
        if(!flag)
            printf("%lld\n",xmn+((a[n]%b[n])+b[n])%b[n]);
    }
    return 0;
}