[LOJ 2721][UOJ 396][BZOJ 5418][NOI 2018]屠龙勇士

题意

~~题面好啰嗦啊直接粘LOJ题面好了~~

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

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

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

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

每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择攻击力最低的一把剑作为武器。

机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 (x) 次，使巨龙的生命值减少 (x imes ATK)。

之后，巨龙会不断使用恢复能力，每次恢复 (p_i) 生命值。若在使用恢复能力前或某一次恢复后其生命值为 (0)，则巨龙死亡，玩家通过本关。

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

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

杀龙的时候需要三步必杀, 不能重复多次qwq...

(nle 10^5,mle 10^5,a_ile 10^{12}).

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

题解

乍一看这题神仙的一匹, 然而冷静分析一下可以发现:

拿来淦龙的剑都是固定的, 而且每次相当于把龙的血打到一个不大于 (0) 的 (p_i) 的倍数就可以完成任务了.

那么也就是说只要让 (x) 满足:

[x imes ATK_iequiv a_i pmod {p_i}\ x imes ATK_ige a_i ]

先来搞第一个限制.

不难发现这个限制相当于下式:

[x imes ATK_i+k imes p_i=a_i ]

其中 (ATK_i,p_i,a_i) 都是确定的, 显然这个东西可以随手 ExGCD 搞一搞解出一个 (mod p_i) 意义下的 (x).

不过注意这一步要对 (ATK_i) 和 (p_i) 进行约分, 不然逆元不唯一就会解出奇怪的东西qaq(~~sb rvalue在这坑了一个小时~~)...

然后我们不难发现我们得到了一堆形如这样的方程组:

[xequiv r_i pmod {p_i} ]

这不裸的 CRT 么?

然而 (p_i) 不互质. 并不能直接 CRT.

考虑 ExCRT. ExCRT 的大体思路是通过 ExGCD 来合并两个同余方程.

假设我们现在有两个同余方程:

[egin{cases} xequiv a &pmod n\ xequiv b &pmod m end{cases} ]

不难发现它等价于:

[egin{cases} x = a + pn\ x = b + qm end{cases} ]

那么也就是说:

[a+pn=b+qm ]

移项可得:

[a-b=qm-pn ]

好了我们可以 ExGCD 了.

算出 (p) 和 (q) 之后可以用 (x=a+pn=b+pm) 算出 (x) 来. 它与所有 (mod gcd(n,m)) 意义下同余的值都是这两个方程的解. 显然我们直接对 (gcd(n,m)) 取模就可以得到最小值了.

一直这样合并下去, 只要 ExGCD 的时候出锅那么根据Bézout定理这个方程组无解.

然后我们可以得到一个 (mod operatorname{lcm} {p_i}) 的 (x). 接着考虑第二种限制.

显然我们可以对当前已有的 (x) 计算它是否满足 (x imes ATK_ige a_i), 如果不满足的话把 (x) 变为 (mod operatorname{lcm} {p_i}) 意义下同余的最小满足条件的值就可以了. 不难发现答案就是:

[x+operatorname{lcm}{p_i} imes max_{1le ile n}left lceil frac {left lceil frac{a_i}{ATK_i} ight ceil-x}{operatorname{lcm}{p_i}} ight ceil ]

UOJ因为有Hack所以数据比LOJ强一些, LOJ过了之后建议在UOJ上交一发.

参考代码

~~下面这份代码在发文时没有被Hack qwq...~~

#include <bits/stdc++.h>

const int MAXN=1e5+10;
typedef long long intEx;

struct Equation{
	intEx mod;
	intEx rest;
};
Equation E[MAXN];

int n;
int m;
intEx a[MAXN];
intEx p[MAXN];
intEx w[MAXN];
intEx atk[MAXN];

intEx Mul(intEx,intEx,intEx);
intEx ExGCD(intEx,intEx,intEx&,intEx&);

int main(){
	int T;
	scanf("%d",&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",w+i);
		std::multiset<intEx> s;
		for(int i=1;i<=m;i++){
			intEx x;
			scanf("%lld",&x);
			s.insert(x);
		}
		try{
			for(int i=1;i<=n;i++){
				E[i].mod=p[i];
				auto it=s.upper_bound(a[i]);
				if(it!=s.begin())
					--it;
				intEx t;
				atk[i]=*it;
				s.erase(it);
				intEx gcd=ExGCD(atk[i],p[i],E[i].rest,t);
				if(a[i]%gcd!=0)
					throw std::logic_error(R"(a[i]%gcd!=0)");
				E[i].mod/=gcd;
				E[i].rest=Mul(a[i]/gcd,E[i].rest,E[i].mod);
				(E[i].rest+=E[i].mod)%=E[i].mod;
				s.insert(w[i]);
			}
			for(int i=2;i<=n;i++){
				intEx x,y;
				intEx gcd=ExGCD(E[i-1].mod,E[i].mod,x,y);
				intEx lcm=E[i-1].mod/gcd*E[i].mod;
				if((E[i-1].rest-E[i].rest)%gcd!=0)
					throw std::logic_error(R"((E[i].rest-E[i-1].rest)%gcd!=0 @)"+std::to_string(i));
				intEx scale=(E[i-1].rest-E[i].rest)/gcd;
				(E[i].rest+=Mul(Mul(scale,y,lcm),E[i].mod,lcm))%=lcm;
				E[i].mod=lcm;
				E[i].rest=(E[i].rest+lcm)%lcm;
			}
			intEx scale=0;
			for(int i=1;i<=n;i++)
				scale=std::max(scale,((a[i]+atk[i]-1)/atk[i]-E[n].rest+E[n].mod-1)/E[n].mod);
			printf("%lld
",E[n].rest+scale*E[n].mod);
		}
		catch(std::logic_error x){
			puts("-1");
			continue;
		}
	}
	return 0;
}

intEx ExGCD(intEx a,intEx b,intEx& x,intEx& y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	intEx gcd=ExGCD(b,a%b,y,x);
	y-=(a/b)*x;
	return gcd;
}

intEx Mul(intEx a,intEx b,intEx p){
	return __int128(a)*b%p;
}