A16847 | $Divisibility Game$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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$，只移除其中一个。无法行动的玩家输掉游戏。 如果双方都采取最优策略，谁会获胜？

每个测试点包含多个测试用例。第一行包含测试用例的数量 $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$。

对于每个测试用例，输出一个单词： - 如果 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

C++ 编辑器

输入

输出