自动搬运

查看原文

来自洛谷，原作者为

	emptysetvvvv 这里埋葬着一位 OIer 的青春

搬运于2025-08-24 22:03:29，当前版本为作者最后更新于2019-06-08 19:19:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

背景

感觉这题还是比较清晰的。

思路

Part I

很明显每条龙对应的剑是确定的，用平衡树处理出第 $i$ 条龙对应的剑的攻击力是 $b_i$，为了方便展示，我就偷懒用 multiset<long long> 实现了。

那么现在题意就转化为，对同余方程组

$$\begin{cases}b_1x\equiv a_1\pmod {p_1}\\b_2x\equiv a_2\pmod {p_2}\\\qquad\cdots\\b_nx\equiv a_n\pmod {p_n}\end{cases} $$

求最小非负整数解。

需要注意的是，要保证可以把龙血砍成负的，即 $x$ 不能小于将每条龙砍成负血的最小刀数。

Part II

在此之前，不妨先想想普通的扩展中国剩余定理是怎么做的，即所有 $b_i=1$ 的情况。

1. 假设已经得到了前 $i-1$ 组同余方程的解，记为 $ans$；
2. 设 $M=\operatorname{lcm}(p_1,p_2,\ldots,p_{i-1})$，则对于任意的整数 $x$，$ans+Mx$ 是前 $i-1$ 组同余方程的通解；
3. 我们想得到前 $i$ 组同余方程的解，就是想找到一个 $x$，满足 $ans+Mx\equiv a_i\pmod {p_i}$；
4. 移项得 $Mx\equiv a_i-ans\pmod{p_i}$；
5. 这类式子一看就是老扩欧了，转化成 $Ax+By=C$ 的形式用扩展欧几里得求解，即：

$$(M)x+(p_i)y=(a_i-ans)$$

Part III

那么有系数 $b_i$ 怎么搞呢？逆元是不可能逆元的，又不互质，在模 $p_i$ 意义下 $b_i$ 未必有逆元。

害，其实还是换汤不换药呗。

1. 假设已经得到了前 $i-1$ 组同余方程的解，记为 $ans$；
2. 设 $M=\operatorname{lcm}(p_1,p_2,\ldots,p_{i-1})$，则对于任意的整数 $x$，$ans+Mx$ 是前 $i-1$ 组同余方程的通解；
3. 想得到前 $i$ 组同余方程的解，就是想找到一个 $x$，满足 $b_i(ans+Mx)\equiv a_i\pmod {p_i}$；
4. 移项得 $b_iMx\equiv a_i-b_ians\pmod{p_i}$；
5. 这类式子一看就是老扩欧了，转化成 $Ax+By=C$ 的形式用扩展欧几里得求解，即：

$$(b_iM)x+(p_i)y=(a_i-b_ians)$$

Part IV

几点注意事项：

1. 判无解就跟平常扩欧的判解一样，若 $C$ 不是 $\gcd(A,B)$ 的倍数，则无解，即若 $a_i-b_ians$ 不是 $\gcd(b_iM,p_i)$ 的倍数，则无解；
2. 看下数据范围，明显有两处需要龟速乘的，鉴于大家都会，我就偷懒用 __int128 实现了。

代码

#include <set>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 100005;
int T, n, m, b[maxn], t[maxn];
long long a[maxn], p[maxn], mx;
multiset<long long> s;
void exgcd(long long A, long long B, long long &x, long long &y, long long &gcd) {
	if(!B) x = 1, y = 0, gcd = A;
	else exgcd(B, A%B, y, x, gcd), y -= (A/B) * x;
}
long long ExCRT() {
	long long ans = 0, lcm = 1, x, y, gcd, A, B, C;
	for(int i = 1; i <= n; ++i) {
		A = (__int128)b[i] * lcm % p[i];
		B = p[i];
		C = (a[i]-b[i]*ans%p[i]+p[i]) % p[i];
		exgcd(A, B, x, y, gcd), x = (x%B+B) % B;
		if(C % gcd) return -1;
		ans += (__int128)(C/gcd) * x % (B/gcd) * lcm % (lcm*=B/gcd);
		ans %= lcm;
	}
	if(ans < mx) ans += ((mx-ans-1)/lcm+1) * lcm;
	return ans;
}
int main() {
	scanf("%d", &T);
	while(T--) {
		s.clear(), mx = 0;
		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("%d", &t[i]);
		for(int i = 1, x; i <= m; ++i) scanf("%d", &x), s.insert(x);
		for(int i = 1; i <= n; ++i) {
			auto u = s.upper_bound(a[i]);
			if(u != s.begin()) u--;
			b[i] = *u, s.erase(u), s.insert(t[i]);
			mx = max(mx, (a[i]-1)/b[i]+1);
		}
		printf("%lld\n", ExCRT());
	}
}

P.S.

其实 emptyset 不懒，只是这样比较方便在题解区展示啦。

emptyset 自己 yy 的做法，有 hack 数据可以叫她（有点担心溢出的问题）。

觉得还不错的话点个赞吧。