#include #include #include #include // For std::hash using namespace std; // Custom hash for tuple for unordered_map struct TupleHash { size_t operator()(const tuple& t) const { auto hash1 = hash{}(get<0>(t)); auto hash2 = hash{}(get<1>(t)); auto hash3 = hash{}(get<2>(t)); // Simple combination of hashes - can be improved for better distribution size_t seed = 0; seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2); seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2); seed ^= hash3 + 0x9e3779b9 + (seed << 6) + (seed >> 2); return seed; } }; // Using unordered_map for memoization: key is tuple // unordered_map generally provides faster average time complexity for lookups and insertions // compared to std::map, which can help with runtime performance. unordered_map, bool, TupleHash> memo; // Function to determine if the current player can win from state (a, b) // a: Alice's number, b: Bob's number, is_alice_turn: true if Alice's turn, false if Bob's // Returns: true if current player wins, false otherwise bool solve(long long a, long long b, bool is_alice_turn) { // Base case: If either number is 0, the player whose turn it is *now* loses. // This is because the previous player successfully made their opponent's number zero. if (a == 0 || b == 0) { return false; } // Check if this state has been computed before using memoization tuple current_state = {a, b, is_alice_turn}; if (memo.count(current_state)) { return memo[current_state]; } bool can_win = false; // Assume the current player loses initially if (is_alice_turn) { // Alice's turn, she has 'a', Bob has 'b'. // Alice wins if any of her possible moves lead to a state where Bob loses. // Option 1: Alice subtracts 1 from her number (a). New state: (a-1, b). Bob faces (a-1, b). // This move is always possible if a > 0, which is true due to the base case. if (!solve(a - 1, b, false)) { can_win = true; // Alice wins if Bob loses from (a-1, b) } // Option 2: Alice applies modulo on her number (a % b), if a >= b. New state: (a%b, b). Bob faces (a%b, b). // Only evaluate this move if Alice hasn't already found a winning move (by subtraction). if (!can_win && a >= b) { // Immediate win condition by modulo: if a % b == 0 (and b > 0) or b == 1, // Alice's number becomes 0 (a%b = 0), state becomes (0, b). // Bob faces (0, b). Since 0 is present, Bob loses (base case). Alice wins. if (b == 1 || a % b == 0) { can_win = true; // Immediate win for Alice by modulo } else { // a%b > 0 and b > 1 // Optimization for a >= 2*b: // If a is significantly larger than b, the outcome depends on the // outcome of the game from (a%b, b) and the parity of the quotient a/b. // This is a specific property derived from the game mechanics. if (a >= 2 * b) { // Alice wins if Bob loses from (a%b, b) OR if the quotient (a/b) is even. can_win = (!solve(a % b, b, false)) || ((a / b) % 2 == 0); } else { // a >= b && a < 2*b (Ratio is between 1 and 2), a%b != 0, b > 1 // Alice wins if Bob loses from (a%b, b) if (!solve(a % b, b, false)) { can_win = true; } } } } } else { // Bob's turn, he has 'b', opponent Alice has 'a'. Symmetric logic. // Bob wins if any of his possible moves lead to a state where Alice loses. // Option 1: Bob subtracts 1 from his number (b). New state: (a, b-1). Alice faces (a, b-1). // This move is always possible if b > 0, which is true due to the base case. if (!solve(a, b - 1, true)) { can_win = true; // Bob wins if Alice loses from (a, b-1) } // Option 2: Bob applies modulo on his number (b % a), if b >= a. New state: (a, b%a). Alice faces (a, b%a). // Only evaluate this move if Bob hasn't already found a winning move (by subtraction). if (!can_win && b >= a) { // Immediate win condition by modulo: if b % a == 0 (and a > 0) or a == 1, // Bob's number becomes 0 (b%a = 0), state becomes (a, 0). // Alice faces (a, 0). Since 0 is present, Alice loses (base case). Bob wins. if (a == 1 || b % a == 0) { can_win = true; // Immediate win for Bob by modulo } else { // b%a > 0 and a > 1 // Optimization for b >= 2*a: // Symmetric property for Bob's turn. if (b >= 2 * a) { // Bob wins if Alice loses from (a, b%a) OR if the quotient (b/a) is even. can_win = (!solve(a, b % a, true)) || ((b / a) % 2 == 0); } else { // b >= a && b < 2*a (Ratio is between 1 and 2), b%a != 0, a > 1 // Bob wins if Alice loses from (a, b%a) if (!solve(a, b % a, true)) { can_win = true; } } } } } // Memoize the result for the current state before returning memo[current_state] = can_win; return can_win; } int main() { // Optimize standard I/O operations ios_base::sync_with_stdio(false); cin.tie(NULL); long long A, B; cin >> A >> B; // Determine if Alice wins starting from state (A, B) on her turn if (solve(A, B, true)) { cout << "Alice" << endl; } else { cout << "Bob" << endl; } return 0; }