【洛谷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;
}