【洛谷P4774】屠龙勇士

题目

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

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

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

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

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

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

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

思路

下文记 \(a[i]\) 表示击杀第 \(i\) 条龙的剑的攻击力，\(b[i]\) 表示第 \(i\) 条龙的血，\(p[i]\) 表示第 \(i\) 条龙的回血能力。

由于初始的剑和击杀每条龙后的剑是固定的，所以我们可以用 multiset 求出 \(a[i]\)。

发现每一档分要么满足 \(b[i]\leq p[i]\)，要么满足 \(p[i]=1\)，显然我们是要分两类做。

p[i]=1

容易发现，我们一定是将龙打到负血，然后让它自己回血回到 \(0\)。

所以答案就是

\[\max(\left \lceil \frac{b[i]}{b[i]}\right \rceil) \]

b[i]≤p[i]

发现这种情况下，任意时刻龙的血量都不可能超过 \(p[i]\)，所以当 \(b[i]\bmod p[i]=0\) 时龙就一定是没血的。

所以我们只需要求出

\[\left\{\begin{matrix}a_1x\equiv b_1\pmod p_1 \\a_2x\equiv b_2\pmod p_2 \\\vdots \\a_nx\equiv b_n\pmod p_n \end{matrix}\right.\]

的解。

但是中国剩余定理不可以处理未知项系数不为 \(1\) 的同余方程组，所以要把这个同余方程组变一下。

考虑一个同余方程

\[ax\equiv b\pmod p \]

等价于

\[ax+bp=b \]

那么如果 \(\gcd(a,p)\nmid b\) 该同余方程组就无解，输出

-1

即可。否则用扩欧可以求出 \(x,y\) 的一组整数解 \(x',y'\)。

假设我们要增加 \(x\)，那么必须减小 \(y\) 才能使得方程等号两边相等。容易发现，加号左右两项至少要增减 \(\operatorname{lcm}(a,p)\) 才可以使等号成立，所以必须有

\[x\equiv x'\pmod {\frac{\operatorname{lcm}(a,p)}{a}} \]

也就等价于

\[x\equiv x'\pmod {\frac{p}{\gcd(a,p)}} \]

所以我们可以将原来的同余方程组变为

\[\left\{\begin{matrix}x\equiv b_1\pmod {\frac{p_1}{\gcd{a_1,p_1}}} \\x\equiv b_2\pmod {\frac{p_2}{\gcd{a_2,p_2}}} \\\vdots \\x\equiv b_n\pmod {\frac{p_n}{\gcd{a_n,p_n}}} \end{matrix}\right.\]

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100010;
int n,m,Q;
ll b1,p1,sump,a[N],b[N],c[N],p[N];
bool flag;
multiset<ll> sw;

ll read()
{
	ll d=0,f=1; char ch=getchar();
	while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
	while (isdigit(ch)) d=(d<<3)+(d<<1)+ch-48,ch=getchar();
	return d*f;
}

ll mul(ll x,ll k,ll mod)
{
	ll ans=0;
	for (;k;k>>=1,x=x*2%mod)
		if (k&1) ans=(ans+x)%mod;
	return ans;
}

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

bool excrt(ll b2,ll p2)
{
	ll x,y,d=exgcd(p1,p2,x,y),p=p1/d*p2;
	if ((b2-b1)%d) return 0;
	x=mul(x,((b2-b1)/d%p+p)%p,p);
	b1=(b1+mul(x,p1,p))%p;
	p1=p;
	return 1;
}

void solve1()
{
	ll maxn=0;
	for (int i=1;i<=n;i++)
		maxn=max(maxn,(b[i]-1)/a[i]+1);
	printf("%lld\n",maxn);
}

void solve2()
{
	flag=1;
	for (int i=1;i<=n;i++)
	{
		ll x,y,d=exgcd(a[i],p[i],x,y);
		if (b[i]%d) { flag=0; break; }
		p[i]=p[i]/d;
		x=(x%p[i]+p[i])%p[i];
		b[i]=mul(x,b[i]/d,p[i]);
	}
	if (!flag) { printf("-1\n"); return; }
	b1=b[1]; p1=p[1];
	for (int i=2;i<=n;i++)
		if (!excrt(b[i],p[i])) { flag=0; break; }
	if (flag) printf("%lld\n",(b1%p1+p1)%p1);
		else printf("-1\n");
}

int main()
{
	Q=read();
	while (Q--)
	{
		sw.clear();
		n=read(); m=read();
		sump=0;
		for (int i=1;i<=n;i++) b[i]=read();
		for (int i=1;i<=n;i++) p[i]=read(),sump+=p[i];
		for (int i=1;i<=n;i++) c[i]=read();
		for (int i=1;i<=m;i++) sw.insert(read());
		for (int i=1;i<=n;i++)
		{
			multiset<ll>::iterator p=sw.upper_bound(b[i]);
			if (p==sw.begin()) a[i]=*p;
				else a[i]=*(--p);
			sw.erase(p); sw.insert(c[i]);
		}
		if (sump==n) solve1();
			else solve2();
	}
	return 0;
}