#include #include #include #include #include using namespace std; // Using map for memoization: key is tuple map, bool> 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* did not make it 0. // The player who made it 0 in the previous turn won. So the current player loses. if (a == 0 || b == 0) { return false; } // Check if this state has been computed before tuple current_state = {a, b, is_alice_turn}; if (memo.count(current_state)) { return memo[current_state]; } bool can_win; // Whether the current player can win from this state if (is_alice_turn) { // Alice's turn, she has 'a', Bob has 'b'. // Option 1: Subtract 1 from Alice's number. New state (a-1, b), Bob's turn. // Alice wins by subtract if Bob loses from (a-1, b). bool can_win_sub = !solve(a - 1, b, false); // Option 2: Modulo (only if a >= b). New state (a % b, b), Bob's turn. // Alice wins by modulo if a % b == 0 (immediate win), or if Bob loses from (a%b, b) (if a%b > 0). bool can_win_mod = false; // Default: cannot win by modulo (either not possible or leads to loss) bool modulo_possible = (a >= b); if (modulo_possible) { if (b == 1) { // If Bob's number is 1, Alice can do a % 1 = 0 can_win_mod = true; } else if (a % b == 0) { // Modulo results in 0 can_win_mod = true; } else { // Modulo results in non-zero (a%b > 0) // Optimization: If Alice's number (a) is much larger than Bob's (b), // specifically a >= 2*b, and the modulo move (a%b, b) leads to Bob winning, // the outcome depends on the parity of the quotient a/b. if (a >= 2 * b) { // Alice wins if Bob loses from (a%b, b) OR (Bob wins from (a%b, b) AND (a/b) is even) // Simplified: Alice wins if (!solve(a%b, b, false)) || ((a / b) % 2 == 0) can_win = (!solve(a % b, b, false)) || ((a / b) % 2 == 0); // If the optimization was applied, the outcome is determined. // Do NOT memoize this specific result as it relies on quotient parity which isn't in the key. return can_win; // Directly return the optimized result } else { // a >= b but a < 2*b (Ratio is 1) - no optimization, check modulo path recursively can_win_mod = !solve(a % b, b, false); // Alice wins by modulo if Bob loses from (a%b, b) } } } // Combine possible winning moves (modulo and subtract) // If modulo was not possible, or no immediate win by modulo, check if either move is winning. if (!modulo_possible || (!can_win_mod && modulo_possible && a % b != 0 && a < 2*b) || (!modulo_possible && a < b)) { // If modulo was not possible, or we are in the a < 2*b non-zero remainder case, check both. // If modulo gave immediate win (b=1 or a%b=0), can_win_mod is true. // If a >= 2b and optimization applied, we already returned. if (modulo_possible && (b == 1 || a % b == 0)) { can_win = true; // Immediate win by modulo } else if (modulo_possible && a >= b && a < 2*b && a%b != 0) { can_win = can_win_mod || can_win_sub; // Check both modulo path outcome and subtract path outcome } else if (a < b) { // Only subtract possible can_win = can_win_sub; } else { // Should not reach here if logic is correct // This case covers a >= b, b > 1, a%b != 0, a >= 2b - handled by direct return above // or a >= b, b > 1, a%b == 0 - handled by immediate win above // or a >= b, b == 1 - handled by immediate win above // or a >= b, a < 2b, b > 1, a%b != 0 - handled by (modulo_possible && a >= b && a < 2*b && a%b != 0) // or a < b - handled by (a < b) // It seems the logic branches above cover all cases correctly. // This final 'else' should ideally not be needed if all branches are exhaustive. // Let's re-structure slightly to be clearer. } } else { // This means modulo was possible and led to an immediate win (b=1 or a%b=0), or we are in the a >= 2b optimized case. // If modulo was an immediate win, can_win_mod is true, and can_win is true. // If a >= 2b optimization applied, we already determined can_win and returned. // This else block seems redundant with the structure above. } // Let's simplify the structure based on the main conditions: a=b && a<2b, a>=b && a>=2b. if (a < b) { can_win = !solve(a - 1, b, false); } else { // a >= b if (b == 1 || a % b == 0) { can_win = true; // Immediate win by modulo } else if (a < 2 * b) { // a >= b, b > 1, a%b != 0, a < 2b can_win = !solve(a % b, b, false) || !solve(a - 1, b, false); } else { // a >= 2*b, b > 1, a%b != 0 // Apply optimization can_win = (!solve(a % b, b, false)) || ((a / b) % 2 == 0); // Do NOT memoize this specific result memo[current_state] = can_win; // Still memoize this state's outcome *after* calculation return can_win; // Directly return the optimized result } } } else { // Bob's turn, he has 'b', opponent Alice has 'a'. Symmetric logic. if (b < a) { can_win = !solve(a, b - 1, true); } else { // b >= a if (a == 1 || b % a == 0) { can_win = true; // Immediate win by modulo } else if (b < 2 * a) { // b >= a, a > 1, b%a != 0, b < 2a can_win = !solve(a, b % a, true) || !solve(a, b - 1, true); } else { // b >= 2*a, a > 1, b%a != 0 // Apply optimization can_win = (!solve(a, b % a, true)) || ((b / a) % 2 == 0); // Do NOT memoize this specific result memo[current_state] = can_win; // Still memoize this state's outcome *after* calculation return can_win; // Directly return the optimized result } } } // Memoize if the optimized rule was NOT applied in this call memo[current_state] = can_win; return can_win; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long long A, B; cin >> A >> B; if (solve(A, B, true)) { cout << "Alice" << endl; } else { cout << "Bob" << endl; } return 0; }