#include // 用于标准输入输出流 #include // 虽然未使用,但通常包含在C++标准库中 #include // 虽然未使用,但包含一些数值算法 #include // 用于存储记忆化结果 (关键) #include // 用于 std::pair (map的键) #include // 用于 std::swap (如果需要,但这里未使用) // 使用 long long 类型处理可能达到 10^18 的大整数 using ll = long long; // 使用 map 进行记忆化 // 键是游戏状态 (a, b) 对, 值是布尔类型, 表示当前玩家是否能从此状态获胜 // key是(当前玩家的数, 对手的数) std::map, bool> memo; // 函数 can_win(a, b): 判断当前轮到的玩家 (持有数字 a, 对手持有数字 b) 是否有必胜策略 bool can_win(ll a, ll b) { // 基本情况 1: 如果当前玩家的数字 a <= 0 // 轮到你时你的数字已经是0或负数(理论上不会负),意味着你在对手的回合后数字变成了0或更少。 // 根据规则 "先将自己数字变成 0 者获胜",你已经输了。 if (a <= 0) { return false; // 输了 } // 基本情况 2: 如果对手的数字 b <= 0 // 这意味着对手在他/她的上一个回合使得 b 变成了 0 或更少。 // 对手获胜了。所以当前玩家面临 (a, b<=0) 这个状态时,实际上已经输了。 if (b <= 0) { return false; // 输了 } // 检查记忆化表: 如果状态 (a, b) 已经计算过, 直接返回存储的结果 std::pair state = {a, b}; if (memo.count(state)) { return memo[state]; } // 优化: 如果 a >= 2 * b, 那么当前玩家总能获胜. (这里需要 b > 0, 前面的检查已保证) // 这个优化是解决内存和时间限制的关键。它基于对这类博弈(类似欧几里得博弈)的分析, // 即使规则略有不同(多了减1操作),这个条件通常能保证存在获胜策略。 // 我们接受这个常见的优化结论。 if (a >= 2 * b) { // 记录结果并返回 true memo[state] = true; return true; } // 递归计算: 当前玩家获胜,当且仅当存在一个操作,使得操作后的状态对于下一个玩家(即当前对手)来说是必败的。 // 必败状态意味着对手视角的 can_win 调用返回 false。 // 考虑操作 1: 将自己的数减 1 (a -> a - 1) // 操作后, 对手将面临状态 (b, a - 1). // 当前玩家获胜,如果对手从 (b, a - 1) 状态出发无法获胜 (即 can_win(b, a - 1) == false). // 获胜条件: !can_win(b, a - 1) if (!can_win(b, a - 1)) { // 找到了一个获胜策略, 记录结果并返回 true memo[state] = true; return true; } // 考虑操作 2: 将自己的数替换为 a % b (仅当 a >= b 时可行) // 注意: 由于 a >= 2*b 的情况已被上面的优化处理,如果能执行到这里且 a >= b, // 那么必然有 b <= a < 2*b. if (a >= b) { ll remainder = a % b; // 操作后, 对手将面临状态 (b, remainder). // 当前玩家获胜, 如果对手从 (b, remainder) 状态出发无法获胜 (即 can_win(b, remainder) == false). // 获胜条件: !can_win(b, remainder) // 特别地, 如果 remainder == 0, 那么对手面临 (b, 0). can_win(b, 0) 返回 false. // 此时 !can_win(b, 0) 为 true, 表示当前玩家通过此操作直接获胜,逻辑正确。 if (!can_win(b, remainder)) { // 找到了一个获胜策略, 记录结果并返回 true memo[state] = true; return true; } } // 如果尝试了所有可能的操作, 都无法保证让对手进入必败状态 // (即所有操作都导向对手的必胜状态), 那么当前玩家处于必败状态. // 记录结果并返回 false memo[state] = false; return false; } int main() { // 加速 C++ 标准输入输出流 (在处理大量输入输出时可以提高效率) std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); ll a, b; // 定义长整型变量存储输入的 A 和 B std::cin >> a >> b; // 读取输入 // Alice 是先手, 初始状态是 (A, B). 调用 can_win(a, b) 判断 Alice 是否能赢. if (can_win(a, b)) { // 如果 can_win(a, b) 返回 true, 说明 Alice 有必胜策略 std::cout << "Alice" << std::endl; } else { // 如果 can_win(a, b) 返回 false, 说明 Alice 没有必胜策略, 因此 Bob 获胜 std::cout << "Bob" << std::endl; } return 0; // 程序正常结束 }