A16847. Divisibility Game
编程题
普及/提高-
知识点
题目描述
Alice 和 Bob 正在玩一个游戏。他们有一个数组 $a$ 包含 $n$ 个元素，还有一个数组 $b$ 包含 $m$ 个元素。
玩家轮流行动。Alice 先手。轮到一位玩家时，他们从数组 $a$ 中选择一个数字 $x$，从数组 $b$ 中选择一个数字 $y$。Alice 和 Bob 各自有自己选择 $x$ 和 $y$ 的规则：
- Alice 必须选择 $x$ 和 $y$，使得 $y$ 能被 $x$ 整除。
- Bob 必须选择 $x$ 和 $y$，使得 $y$ 不能被 $x$ 整除。
选择 $x$ 和 $y$ 之后，$y$ 会从数组 $b$ 中移除（但 $x$ 保留在 $a$ 中）。当 $y$ 从 $b$ 中移除时，如果存在多个相同的 $y$，只移除其中一个。无法行动的玩家输掉游戏。
如果双方都采取最优策略，谁会获胜？
玩家轮流行动。Alice 先手。轮到一位玩家时，他们从数组 $a$ 中选择一个数字 $x$，从数组 $b$ 中选择一个数字 $y$。Alice 和 Bob 各自有自己选择 $x$ 和 $y$ 的规则：
- Alice 必须选择 $x$ 和 $y$，使得 $y$ 能被 $x$ 整除。
- Bob 必须选择 $x$ 和 $y$，使得 $y$ 不能被 $x$ 整除。
选择 $x$ 和 $y$ 之后，$y$ 会从数组 $b$ 中移除（但 $x$ 保留在 $a$ 中）。当 $y$ 从 $b$ 中移除时，如果存在多个相同的 $y$，只移除其中一个。无法行动的玩家输掉游戏。
如果双方都采取最优策略，谁会获胜？
输入格式
每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^{6}$）。
每个测试用例的第二行包含 $n$ 个整数 $a_{i}$（$1 \le a_{i} \le n + m$）——数组 $a$ 的元素。
每个测试用例的最后一行包含 $m$ 个整数 $b_{i}$（$1 \le b_{i} \le n + m$）——数组 $b$ 的元素。
输入的附加约束：
- 所有测试用例中 $n$ 的总和不超过 $10^6$；
- 所有测试用例中 $m$ 的总和不超过 $10^6$。
每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^{6}$）。
每个测试用例的第二行包含 $n$ 个整数 $a_{i}$（$1 \le a_{i} \le n + m$）——数组 $a$ 的元素。
每个测试用例的最后一行包含 $m$ 个整数 $b_{i}$（$1 \le b_{i} \le n + m$）——数组 $b$ 的元素。
输入的附加约束：
- 所有测试用例中 $n$ 的总和不超过 $10^6$；
- 所有测试用例中 $m$ 的总和不超过 $10^6$。
输出格式
对于每个测试用例，输出一个单词：
- 如果 Alice 获胜，输出
- 如果 Bob 获胜，输出
- 如果 Alice 获胜，输出
Alice；- 如果 Bob 获胜，输出
Bob。输入输出样例
输入 #1
3 9 3 3 2 4 2 2 4 4 2 4 6 7 12 10 3 3 2 5 4 2 5 3 4 4 4 10 7 13 1 5 1 1 2 3 4 5
输出 #1
Alice Bob Alice
说明/提示
考虑第一个测试用例。让我们演示 Alice 如何通过操作获胜：
- Alice 的回合：$x = 3, y = 6$（此后，$6$ 将从 $b$ 中移除，结果是 $b = [7, 12]$）
- Bob 的回合：$x = 3, y = 7$（Bob 还是会选择 $y = 7$，因为没有 $x$ 使得 $y = 12$ 不被整除；这次操作后 $b = [12]$）
- Alice 的回合：$x = 4, y = 12$（这次操作后，$b$ 变为空）
- Bob 的回合：Bob 无法行动，输掉游戏
- Alice 的回合：$x = 3, y = 6$（此后，$6$ 将从 $b$ 中移除，结果是 $b = [7, 12]$）
- Bob 的回合：$x = 3, y = 7$（Bob 还是会选择 $y = 7$，因为没有 $x$ 使得 $y = 12$ 不被整除；这次操作后 $b = [12]$）
- Alice 的回合：$x = 4, y = 12$（这次操作后，$b$ 变为空）
- Bob 的回合：Bob 无法行动，输掉游戏