题解：AT_arc145_b [ARC145B] AB Game

Nirvana_Ethereal · 2026-04-25 14:28:13 · 题解

ARC145B AB Game 题解

题目大意

Alice 和 Bob 进行取石子游戏，规则如下：

1. 初始有 n 个石子，Alice 先手；
2. Alice 操作：只能取走 A 的正整数倍个石子；
3. Bob 操作：只能取走 B 的正整数倍个石子；
4. 无法操作的一方判负。

给定整数 N,A,B，请求出游戏 1,2,\dots,N 中，双方均采取最优策略时，Alice 获胜的游戏数量。

分析

我们基于最优策略推导 Alice 的必胜条件：

1. Alice 的最优操作

• 若石子数 x < A：Alice 无法取石子，直接失败；
• 若石子数 x \ge A：Alice 会取走最大的 A 的倍数，剩余石子数为 x \bmod A（留给 Bob 最小的石子数）。

2. Bob 的操作判定

设剩余石子数 r = x \bmod A：

• 若 r < B：Bob 无法取石子，Alice 获胜；
• 若 r \ge B：Bob 可以正常操作，Alice 必败。

最后得出：

Alice 必胜的充要条件：

代码在其它题解中已有给出，这里不再赘述。