【洛谷-P7835】「Wdoi-3」夜雀 dreaming • TonyYin's Blog

考场解法，比其他题解复杂，但好像顺便说明了其他题解的结论？

题意#

剪贴板 ↗ 里的题目描述比较友好。

有无限个盒子，从 $1$ 开始编号，有 $n$ 个球，从 $0$ 开始编号。有 $k$ 个人。

$k$ 个人往盒子里放球，第 $i$ 个人只能在编号为 $t_i$ 的倍数的盒子放球，第 $j$ 次放球的颜色编号为 $[x_i+(j-1)\times y_i]\bmod n$ .

求：编号最小的盒子，满足盒子里存在两球颜色不同。

$n\leq 10^9$ ， $k\leq 10^3$ .

分析#

注意到 $k\leq 10^3$ ，容易想到暴力枚举两个人，设这两人为 $(u, v)$ .

$u$ 和 $v$ 会在一些盒子里同时放球，这些盒子的编号为 $c\times \operatorname{lcm}(t_u, t_v)$ ， $c$ 是正整数。

对于第 $c\times \operatorname{lcm}(t_u, t_v)$ 个盒子，是 $u$ 第 $\dfrac{\operatorname{lcm}(t_u, t_v)}{t_u}\times c$ 次放球，是 $v$ 第 $\dfrac{\operatorname{lcm}(t_u, t_v)}{t_v}\times c$ 次放球。

对于某个 $c$ ，假设第 $c\times \operatorname{lcm}(t_u, t_v)$ 个盒子中， $u$ 和 $v$ 所放球的颜色相同，那么有同余方程：

x_u+(c\times \frac{\operatorname{lcm}(t_u, t_v)}{t_u}-1)\cdot y_u \equiv x_v+(c\times \frac{\operatorname{lcm}(t_u, t_v)}{t_v}-1)\cdot y_v \pmod{n}

其中只有 $c$ 是未知量，整理一下式子，即可用 $\rm{ExGcd}$ 求出 $c$ 的最小正整数解 $c_{min}$ .

若 $c_{min}\geq 2$ ，说明第 $\operatorname{lcm}(t_u, t_v)$ 个盒子满足条件，用 $\operatorname{lcm}(t_u, t_v)$ 更新答案。

若 $c_{min}=1$ ，继续判断 $c=2$ 是否为可行解。若 $c\neq 2$ ，则用 $2\times \operatorname{lcm}(t_u, t_v)$ 更新答案。否则 $(u, v)$ 这种情况无解，对答案无贡献。

代码#

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1008;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, k;
inline int exgcd(int a, int b, int &x, int &y) {
	if(b == 0) {
		x = 1, y = 0;
		return a;
	}
	int r = exgcd(b, a % b, x, y);
	int t = x;
	x = y;
	y = t - a / b * y;
	return r;
}
inline int gcd(int a, int b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}
int t[MAXN], x[MAXN], y[MAXN];
signed main() {
	scanf("%lld%lld", &n, &k);
	for(int i = 1; i <= k; i++) {
		scanf("%lld%lld%lld", &t[i], &x[i], &y[i]);
	}
	int ans = inf;
	for(int i = 1; i <= k; i++) {
		for(int j = 1; j <= k; j++) {
			if(i == j) continue;
			int xx, yy;
			int Lcm = t[i] / gcd(t[i], t[j]) * t[j];
			int a = Lcm / t[i] * y[i] - Lcm / t[j] * y[j];
			int b = x[j] - x[i] + y[i] - y[j];
			if(a < 0 && b < 0) continue;
			int d = gcd(a, n);
			if(b % d != 0) {
				ans = min(ans, Lcm);
				continue;
			} else {
				exgcd(a, n, xx, yy);
				int tmp = ((b/d*xx) % (n/d) + (n/d)) % (n/d);
				if(tmp >= 2) ans = min(ans, Lcm);
				if(tmp == 1 && (n/d) != 1) {
					ans = min(ans, 2 * Lcm);
				}
			}
		}
	}
	if(ans == inf) cout << "Mystia will cook forever...\n";
	else cout << ans - 1 << endl;
	return 0;
}

cpp