【洛谷P4774】屠龙勇士

题目

题目链接：https://www.luogu.com.cn/problem/P4774
小 D 最近在网上发现了一款小游戏。游戏的规则如下：

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

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

每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择 攻击力最低 的一把剑作为武器。
机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 (x) 次，使巨龙的生命值减少 (x imes 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]} ight ceil) ]

b[i]≤p[i]

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

[left{egin{matrix}a_1xequiv b_1pmod p_1 \a_2xequiv b_2pmod p_2 \vdots \a_nxequiv b_npmod p_n end{matrix} ight.]

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

[axequiv bpmod p ]

等价于

[ax+bp=b ]

那么如果 (gcd(a,p) mid b) 该同余方程组就无解，输出 -1 即可。否则用扩欧可以求出 (x,y) 的一组整数解 (x',y')。
假设我们要增加 (x)，那么必须减小 (y) 才能使得方程等号两边相等。容易发现，加号左右两项至少要增减 (operatorname{lcm}(a,p)) 才可以使等号成立，所以必须有

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

也就等价于

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

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

[left{egin{matrix}xequiv b_1pmod {frac{p_1}{gcd{a_1,p_1}}} \xequiv b_2pmod {frac{p_2}{gcd{a_2,p_2}}} \vdots \xequiv b_npmod {frac{p_n}{gcd{a_n,p_n}}} end{matrix} ight.]

然后就是 ExCRT 的模板了。直接做 (n-1) 次扩欧即可。
时间复杂度 (O(Tnlog n))。

代码

#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
",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
"); 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
",(b1%p1+p1)%p1);
		else printf("-1
");
}

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;
}