「Wdoi2021」Windy OI Round3 ">「Wdoi2021」Windy OI Round3 "> Luogu – P7835 -「Wdoi-3」夜雀 dreaming - TonyYin - Blog
Luogu – P7835 -「Wdoi-3」夜雀 dreaming

题意

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

有无限个盒子,从 $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;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇