题解

思路

只要当前玩家还有至少两张牌，就不可能所有选择都会立刻失败：若两张不同牌加到当前总和后都为 $M$ 的倍数，它们之差也会被 $M$ 整除，但牌面都在 $1$ 到 $N<M$ 内，这是不可能的。

做法

因此决定胜负的是 Alice 打出自己最后一张牌的时刻。若 Bob 最后保留的牌是 $x$，此时场上总和为两副牌的总和减去 $x$，即 $N(N+1)-x$；Bob 能获胜当且仅当存在 $1\le x\le N$ 使它被 $M$ 整除。

令 $R=N(N+1)\bmod M$。由于 $0\le R<M$ 且 $N<M$，上述 $x$ 若存在只能等于 $R$，所以当且仅当 $1\le R\le N$ 时输出 Bob，否则输出 Alice。

复杂度

每组询问时间复杂度为 $O(1)$，额外空间复杂度为 $O(1)$；乘法使用 64 位整数即可安全容纳。