UOJ#396. 【NOI2018】屠龙勇士

http://uoj.ac/problem/396

## 一、一些小处理

首先，每一条龙该使用哪一把剑是严格确定的，这个可以用set加lower_bound预处理出来。我们发现，要想打死一条龙，需要满足的条件是：
$$
atk_ix\equiv hp_i(mod\ p_i) 且 atk_ix \geq hp_i
$$
其中$atk_i$是预处理出的攻击力，$hp_i$是巨龙的血量，$p_i$是恢复能力。

对于后面的限制是好做的，只要求出前面同余方程组的解就可以解出满足后面性质的最小解。

对于前面形如$ax\equiv c(mod\ p) $的方程，我们用扩展欧几里得对$x$求解并用模意义表示解集。

具体地说：

$$ax \equiv c (mod\ p) \to ax+py=c$$

我们解出的解集形如：$x=x_0 \pm k\frac{p}{gcd(a,p)}$

进而表示为：$x\equiv x_0 (mod\ \frac{p}{gcd(a,p)})$

现在的问题变成了有多个形如$x\equiv c_i(mod\ p_i)$的同余方程，求他们的共解。

建议把$ax\equiv c(mod\ p) \to x\equiv c_i(mod\ p_i)$写成一个函数，方便调用

## 二、扩展中国剩余定理

$x\equiv c_i(mod\ p_i)$的通解？这不是CRT吗？

然而我们立即会发现，本题中$p_i$不一定是互质的。

有没有其他的办法绕过互质这个条件呢。

考虑一个合并操作，如果对于任意两个式子
$$
x\equiv c_1(mod\ p_1),x\equiv c_2(mod\ p_2)
$$
我们都可以将其合并为$x\equiv c(mod\ p)$的新形式，那么合并到最后，

最后一个同余方程的解集就应该是全局的解集了。

事实上，我们只要对两个合并的式子做类似crt的操作我们就能合并出新式子。

将上面的同余方程转换为一般形式：
$$
x = c_1+p_1k_1,x = c_2+p_2k_2
$$

$$
c_1+p_1k_1 = c_2+p_2k_2\to p_1k_1-p_2k_2 = c_2-c_1
$$

联立两式，我们希望求出$x$的一个解，所以只需要找到任意一个合法的$k_1$即可，这样就能往回带算出一个合法的$x$了，这里可以调用$exgcd$。

但是有没有更优美的写法呢？

注意到我们之前实现了$ax\equiv c(mod\ p) \to x\equiv c_i(mod\ p_i)$

事实上
$$
p_1k_1-p_2k_2 = c_2-c_1\leftrightarrow p_1k_1\equiv c_2-c_1(mod\ p_2)
$$
我们调用刚才那个函数就能解出$k_1$了！同时我们找到了$x$的一个解$x_0$。

这一个解有什么用呢？类似crt的，我们发现解集其实就是$x_0\pm lcm(p1,p2)$ ，

这样每一次加的是$p1,p2$的最小公倍数，对在$(mod p1),(mod p2)$意义下的值都没有影响。

于是我们合并出了新方程：$x\equiv x_0(mod\ lcm(p1,p2))$。

所以题目给出了所有数的$lcm$不大于$10^{12}$的条件。

这样我们求出最后合并出的方程的解集，并找到满足$atk_ix \geq hp_i$的条件的最小解$x$就是答案了。

可以看出扩展中国剩余定理是中国剩余定理理想的替代品，降低了代码难度，封装性更高。

## 三、一些细节

本题$10^{12}$，可能乘爆$long\ long$，需要快速乘。

任何时候，只要$ax\equiv c(mod\ p) \to x\equiv c_i(mod\ p_i)$的函数返回无解，那么整个局面都无解。

建议的扩展中国剩余定理写法：

龟速乘：
```
LL fprod(LL a, LL b, LL p) {
	LL ans = 0;
	while(b) {
		if(b & 1) ans = (ans + a) % p;
		a = (a + a) % p, b >>= 1;
	}
	return ans;
}
```

实现$ax\equiv c(mod\ p) \to x\equiv res(mod\ mod)$转换函数：

```
int GetEqu(LL a, LL c, LL p, LL & mod, LL & res) {
	LL d = gcd(a, p), x, y;
	if(c % d) 
		return -1;
	c = (c % p + p) % p;
	exgcd(a, p, x, y), mod = p / d;
	res = fprod(x, c / d, mod);
	res += mod, res %= mod;
	return 1;
}
```

实现合并的函数：

```
int merge(LL & nr, LL & np, LL r1, LL p1) {
	LL r = nr, p = np, c = r1 - r;
	LL d = gcd(p, p1), k, mod; 
	if(GetEqu(p, c, p1, mod, k) == -1)
		return -1;
	k = (k % mod + mod) % mod;
	np = p / d * p1;
	nr = fprod(p, k, np) + r;
	return 1;
}
```

总的起来，代码：

```
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#define LL long long
using namespace std;

const int maxn = 1e5 + 5;
int n, m;
multiset<LL > st;
multiset<LL >::iterator it;
LL a[maxn], b[maxn], hp[maxn], p[maxn], atk[maxn];
LL res, mods, tmp, t2, mn, FinA, FinB;
LL exgcd(LL a, LL b, LL &x, LL &y) {
	return b ? (exgcd(b, a % b, y, x), (y -= (a / b) * x)) : (x = 1, y = 0);
}
LL gcd(LL a, LL b) {
	return b ? gcd(b, a % b) : a;
}
LL fprod(LL a, LL b, LL p) {
	LL ans = 0;
	while(b) {
		if(b & 1) ans = (ans + a) % p;
		a = (a + a) % p, b >>= 1;
	}
	return ans;
}

int GetEqu(LL a, LL c, LL p, LL & mod, LL & res) {
	LL d = gcd(a, p), x, y;
	if(c % d) 
		return -1;
	c = (c % p + p) % p;
	exgcd(a, p, x, y), mod = p / d;
	res = fprod(x, c / d, mod);
	res += mod, res %= mod;
	return 1;
}

int merge(LL & nr, LL & np, LL r1, LL p1) {
	LL r = nr, p = np, c = r1 - r;
	LL d = gcd(p, p1), k, mod; 
	if(GetEqu(p, c, p1, mod, k) == -1)
		return -1;
	k = (k % mod + mod) % mod;
	LL l = p / d * p1;
	nr = fprod(p, k, l) + r;
	np = l;
	return 1;
}

void solve() {
	scanf("%d%d", &n, &m), mn = 0;
	for(register int i = 1; i <= n; ++i)
		scanf("%lld", &hp[i]);
	for(register int i = 1; i <= n; ++i)
		scanf("%lld", &p[i]);
	for(register int i = 1; i <= n; ++i)
		scanf("%lld", &a[i]);
	st.clear();
	for(register int i = 1; i <= m; ++i)
		scanf("%lld", &tmp), st.insert(tmp);
	for(register int i = 1; i <= n; ++i) {
		it = st.begin();
		if ((tmp = (*it)) > hp[i])
            st.erase(it), atk[i] = tmp;
        else it = st.upper_bound(hp[i]),
            atk[i] = (*--it), st.erase(it);
        st.insert(a[i]);
	}
	FinB = 0, FinA = 1;
	for(register int i = 1; i <= n; ++i) {
		mn = max(mn, (hp[i] + atk[i] - 1) / atk[i]);
		if(GetEqu(atk[i], hp[i], p[i], mods, res) == -1) 
			{printf("-1\n");return ;}
		if(merge(FinB, FinA, res, mods) == -1)
			{printf("-1\n");return;}
	}
	if(FinB < mn) FinB += ((mn - FinB - 1) / FinA + 1) * FinA;
	printf("%lld\n", FinB);
}

int main() {
	int t;
	scanf("%d", &t);
	while(t--) solve();
	return 0;
}
```

~~有了excrt妈妈再也不用担心我crt写跪了~~

Rockdu's Blog

导航

最近发表

大佬们的友链