#include #include #include #include #include using namespace std; typedef long long ll; // memo[0] for Alice's turn, memo[1] for Bob's turn // value is 1 if the player whose turn it is wins, 0 otherwise. map, int> memo[2]; // Returns 1 if the current player (with my_num) wins against opponent (with opp_num), 0 otherwise. // Assumes my_num > 0 and opp_num > 0 when called initially. int solve(ll my_num, ll opp_num, bool is_my_turn) { // If we reach a state where memo already has the answer, return it. pair state = {my_num, opp_num}; int player_idx = is_my_turn ? 0 : 1; if (memo[player_idx].count(state)) { return memo[player_idx][state]; } // Check immediate win conditions for the current player: make my_num = 0 // Move 1: Decrease my_num by 1 if (my_num == 1) { // my_num - 1 becomes 0 return memo[player_idx][state] = 1; // Current player wins } // Move 2: Modulo my_num by opp_num (if possible) if (opp_num <= my_num && my_num % opp_num == 0) { // my_num % opp_num becomes 0 return memo[player_idx][state] = 1; // Current player wins } // If no immediate win, explore non-winning moves. // Current player wins if *any* non-winning move leads to a state where the opponent loses. bool can_win = false; // Option 1: Decrease my_num by 1 (results in my_num - 1 > 0) // New state for opponent: opponent has opp_num, I have my_num - 1. State (opp_num, my_num - 1) for opponent's turn. // Current player wins if solve(opp_num, my_num - 1, !is_my_turn) returns 0 (opponent loses). if (my_num > 1) { // Only consider this move if my_num - 1 > 0 (my_num == 1 is immediate win) if (solve(opp_num, my_num - 1, !is_my_turn) == 0) { can_win = true; } } // If already found a winning move, no need to check others if (can_win) { return memo[player_idx][state] = 1; } // Option 2: Modulo my_num by opp_num (if possible and non-zero). The resulting number my_num' = my_num % opp_num. // New state for opponent: opponent has opp_num, I have my_num % opp_num. State (opp_num, my_num % opp_num) for opponent's turn. // Current player wins if solve(opp_num, my_num % opp_num, !is_my_turn) returns 0 (opponent loses). if (opp_num <= my_num) { // Modulo is possible if (my_num % opp_num != 0) { // If not an immediate win by modulo if (solve(opp_num, my_num % opp_num, !is_my_turn) == 0) { can_win = true; } } } // Store and return result return memo[player_idx][state] = can_win ? 1 : 0; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll A, B; cin >> A >> B; // Alice goes first, has A, Bob has B. // solve(A, B, true) checks if the player with A (Alice) wins starting the game with numbers (A, B). if (solve(A, B, true) == 1) { cout << "Alice" << endl; } else { cout << "Bob" << endl; } return 0; }