#include // 用于标准输入输出流 #include // 用于实现记忆化存储 #include // 用于 std::pair using namespace std; // 使用 unsigned long long 来处理可能非常大的整数 (高达 10^18) typedef unsigned long long ull; // 记忆化表:存储状态 (a, b) 的结果 // 键:pair 表示状态(当前玩家的数字,对手的数字) // 值:bool,如果当前玩家能从该状态获胜则为 true,否则为 false map, bool> memo; // 递归函数,判断当前玩家是否能从状态 (a, b) 获胜 // a: 当前玩家的数字 // b: 对手的数字 bool solve(ull a, ull b) { // 基本情况 1: 当前玩家数字为 0,意味着轮到该玩家时游戏已经结束,他输了。 if (a == 0) return false; // 基本情况 2: 对手数字为 0,意味着轮到当前玩家时,对手已经输了,当前玩家获胜。 if (b == 0) return true; // 检查记忆化表,如果该状态已经计算过,则直接返回结果 pair state = {a, b}; if (memo.count(state)) { return memo[state]; } // 存储当前状态的胜负结果,默认为 false (无法获胜) bool can_win = false; // 优化:如果 a >= 2b,当前玩家存在必胜策略。(b > 0 已由前面的 b == 0 判断保证) // 这个优化常见于类似欧几里得算法的游戏。 if (a >= 2 * b) { can_win = true; } // 情况 1: a < b else if (a < b) { // 唯一的操作是将 a 减 1 ull next_a = a - 1; // 如果减 1 后 a 变为 0,当前玩家立即获胜 if (next_a == 0) { can_win = true; } else { // 否则,当前玩家获胜,当且仅当对手从下一个状态 (b, next_a) 出发会输掉游戏。 // 对手输掉意味着 solve(b, next_a) 返回 false。 can_win = !solve(b, next_a); } } // 情况 2: b <= a < 2b else { // 玩家可以选择两种操作: // 操作 1: a -> a % b ull next_a_mod = a % b; bool win_via_mod = false; // 如果取模后 a 变为 0,当前玩家立即获胜 if (next_a_mod == 0) { win_via_mod = true; } else { // 否则,当前玩家获胜,当且仅当对手从下一个状态 (b, next_a_mod) 出发会输掉游戏。 win_via_mod = !solve(b, next_a_mod); } // 如果通过取模操作已经能获胜,则不必考虑减 1 操作 if (win_via_mod) { can_win = true; } else { // 操作 2: a -> a - 1 ull next_a_sub = a - 1; bool win_via_sub = false; // 如果减 1 后 a 变为 0,当前玩家立即获胜 if (next_a_sub == 0) { win_via_sub = true; } else { // 否则,当前玩家获胜,当且仅当对手从下一个状态 (b, next_a_sub) 出发会输掉游戏。 win_via_sub = !solve(b, next_a_sub); } // 当前玩家获胜,如果减 1 操作能导致获胜(因为取模操作不能) can_win = win_via_sub; } // 最终逻辑:如果存在任何一个操作可以获胜,则当前状态可获胜。 // (上面嵌套的 if-else 已经实现了这个逻辑) // bool final_win_mod = (a % b == 0) || !solve(b, a % b); // bool final_win_sub = (a - 1 == 0) || !solve(b, a - 1); // can_win = final_win_mod || final_win_sub; // 这行代码等价于上面的 if-else 结构 } // 将计算结果存入记忆化表并返回 return memo[state] = can_win; } int main() { // 加速 C++ 输入输出流 ios_base::sync_with_stdio(false); cin.tie(NULL); ull a, b; // Alice 的初始数字 A,Bob 的初始数字 B cin >> a >> b; // 调用 solve(a, b) 来确定 Alice(先手玩家)是否获胜。 if (solve(a, b)) { cout << "Alice" << endl; } else { cout << "Bob" << endl; } return 0; }