Moe's CF Life

Appearance

喵~ 主人，你好呀！今天由本喵来带你分析一道有趣的博弈论题目——Deleting Divisors。这可不是简单的加减乘除哦，里面藏着一些小小的智慧，就像猫咪在角落里发现的毛线球一样，充满了惊喜！一起来看看吧，喵~

【题目大意喵】 ​

爱丽丝 (Alice) 和鲍勃 (Bob) 在玩一个数字游戏。

  1. 游戏开始时有一个正整数 n。
  2. 两人轮流操作，爱丽丝先手。
  3. 每一轮，玩家需要从当前的数字 n 中减去它的一个因子 d。这个因子 d 不能是 1 也不能是 n 本身。
  4. 操作后，n 会变成 n - d，成为下一个玩家面对的数字。
  5. 如果一个玩家轮到他/她时，无法进行任何有效的操作，那么他/她就输了。

假设爱丽丝和鲍勃都绝顶聪明，总会选择最优的策略。我们需要判断谁会赢得这场游戏。

举个栗子，喵~

  • 如果 n = 12：
    • 12 的因子有 1, 2, 3, 4, 6, 12。可以减去的有 2, 3, 4, 6。
    • 爱丽丝可以选择减去 3，n 变成 12 - 3 = 9。
    • 现在轮到鲍勃，n=9。9 的因子有 1, 3, 9。鲍勃只能减去 3，n 变成 9 - 3 = 6。
    • 轮到爱丽丝，n=6。6 的因子有 1, 2, 3, 6。爱丽丝可以减去 3，n 变成 6 - 3 = 3。
    • 轮到鲍勃，n=3。3 的因子只有 1, 3。没有可以减去的因子了，所以鲍勃无法操作，鲍勃输了。
    • 因此，爱丽丝获胜！

【解题思路喵】 ​

这是一道典型的公平组合游戏 (Impartial Game)，我们可以用必胜态和必败态来分析它，喵~

  • 必败态 (Losing Position)：轮到当前玩家时，无论怎么操作，都会让对手进入一个必胜态。如果一个玩家无法操作，那么他所处的也是必败态。
  • 必胜态 (Winning Position)：轮到当前玩家时，存在至少一种操作，可以让对手进入一个必败态。

我们的目标就是，对于给定的 n，判断它是必胜态还是必败态。如果是必胜态，先手的爱丽丝赢；如果是必败态，后手的鲍勃赢。

第一步：分析奇数的情况 ​

如果 n 是一个奇数：

  • 首先，一个奇数的所有因子都必然是奇数。
  • 当爱丽丝操作时，她必须减去一个奇数因子 d。
  • n (奇数) - d (奇数) = 一个偶数。
  • 这意味着，只要 n 是奇数，爱丽丝的任何一步操作都会把一个偶数留给鲍勃。

如果奇数是一个必败态，那么爱丽丝从奇数出发，必然会走到一个偶数。如果鲍勃从这个偶数出发，总能找到一种方法走回一个奇数（也就是让爱丽す进入必败态），那么鲍勃就赢了。

我们大胆猜测：所有奇数都是必败态。 为什么呢？因为对于任何大于1的奇数 n，爱丽丝都无法操作（比如 n 是素数），或者只能移动到一个偶数。如果鲍勃总能从偶数移动到一个奇数，那么鲍勃就能一直把“烫手的山芋”（奇数）丢给爱丽丝。最终爱丽丝会面对一个无法操作的奇数（比如3，5，或者1），然后就输掉了，喵~

所以，如果 n 是奇数，鲍勃赢。

第二步：分析偶数的情况 ​

如果 n 是一个偶数，情况就变得有趣了，喵！爱丽丝先手，她非常想把一个必败态（奇数）丢给鲍勃。

要得到一个奇数，她需要执行 n (偶数) - d (奇数) 的操作。所以问题就变成了：一个偶数 n 是否总有一个大于1的奇数因子 d 呢？

这就要分两种情况讨论了：

情况 2a: n 是偶数，但不是 2 的幂

如果一个偶数 n 不是 2 的幂，那么它一定可以被写成 n = 2^k * m 的形式，其中 k >= 1，m 是一个大于1的奇数。

  • 看，m 就是 n 的一个大于1的奇数因子！
  • 爱丽丝可以减去这个奇数因子 m。新的数变成 n - m。
  • 因为 n 是偶数，m 是奇数，所以 n - m 是一个奇数。
  • 爱丽丝成功地把一个奇数（我们分析出的必败态）丢给了鲍勃。
  • 所以，在这种情况下，爱丽丝赢。

情况 2b: n 是 2 的幂

如果 n 是 2 的幂，即 n = 2^k (其中 k >= 1)。

  • n 的所有因子（除了1）都是偶数（2, 4, 8, ...）。
  • 所以爱丽丝无论减去哪个因子 d，n (偶数) - d (偶数) 的结果仍然是一个偶数。
  • 爱丽丝无法一步把鲍勃推入奇数的必败态了。游戏只能在偶数之间进行。

让我们看看爱丽丝的最佳策略。假设她减去因子 d = 2^j (其中 1 <= j < k)。 新的数是 n' = 2^k - 2^j = 2^j * (2^(k-j) - 1)。

  • 2^(k-j) - 1 是一个奇数。
  • 如果 k-j > 1，那么 2^(k-j) - 1 > 1。这意味着 n' 是一个“偶数但非2的幂”的数。根据我们上面的分析 (情况 2a)，这对于下一个玩家（鲍勃）来说是一个必胜态！爱丽丝才不会这么傻呢，喵~
  • 所以，爱丽丝为了不让鲍勃直接获胜，唯一的选择就是让 k-j = 1，也就是 j = k-1。
    • 这意味着爱丽丝必须减去 d = 2^(k-1) = n/2。
    • 操作后，n 变成了 2^k - 2^(k-1) = 2^(k-1)。

游戏就变成了这样：2^k -> 2^(k-1) -> 2^(k-2) -> ...。 这相当于一个关于指数 k 的倒计时游戏：k -> k-1 -> k-2 -> ...。 当 k=1 (即 n=2) 时，没有合法的因子可以减，所以 n=2 是必败态。

  • 如果开始的 k 是偶数：k (偶) -> k-1 (奇) -> k-2 (偶) -> ... -> 2 -> 1。爱丽丝走第一步，每次都把奇数 k 值留给鲍勃。最后是鲍勃面对 k=1，鲍勃输。所以当 k 是偶数时，爱丽丝赢。
  • 如果开始的 k 是奇数：k (奇) -> k-1 (偶) -> ... -> 3 -> 2 -> 1。爱丽丝走第一步，每次都把偶数 k 值留给鲍勃。最后是爱丽丝面对 k=1，爱丽丝输。所以当 k 是奇数时，鲍勃赢。

总结一下喵 ​

  1. n 是奇数 -> 鲍勃赢。
  2. n 是偶数：
    • n 不是 2 的幂 -> 爱丽丝赢。
    • n 是 2 的幂 (n = 2^k):
      • k 是偶数 -> 爱丽丝赢。
      • k 是奇数 -> 鲍勃赢。

【代码实现喵】 ​

这是用 C++ 实现的逻辑，和我分析的一模一样哦，喵~

cpp
#include <iostream>

// 处理单个测试用例的函数
void solve() {
    long long n;
    std::cin >> n;

    // 情况 1: n 是奇数。
    // 奇数是必败态。
    if (n % 2 != 0) {
        std::cout << "Bob\n";
        return;
    }

    // 情况 2: n 是偶数。
    // 我们将 n 写成 n = 2^k * m 的形式，其中 m 是奇数。
    // 通过不断将 n 除以 2 来找到 k 和 m。
    long long temp_n = n;
    int k = 0;
    while (temp_n > 0 && temp_n % 2 == 0) {
        temp_n /= 2;
        k++;
    }

    if (temp_n > 1) {
        // 情况 2a: n 是偶数，但不是 2 的幂 (m > 1)。
        // 爱丽丝可以减去一个奇数因子，让鲍勃面对一个奇数（必败态）。
        // 所以，爱丽丝赢。
        std::cout << "Alice\n";
    } else { // temp_n == 1
        // 情况 2b: n 是 2 的幂, n = 2^k。
        // 胜负取决于 k 的奇偶性。
        if (k % 2 == 0) {
            // k 是偶数：爱丽丝可以移动到 2^(k-1) (k-1 是奇数)，对鲍勃来说是必败态。
            // 爱丽丝赢。
            std::cout << "Alice\n";
        } else {
            // k 是奇数：轮到爱丽丝时，k是奇数，是必败态。
            // 鲍勃赢。
            std::cout << "Bob\n";
        }
    }
}

int main() {
    // 快速输入输出
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

【知识点小课堂喵】 ​

1. 公平组合游戏 (Impartial Game) 与 P/N 分析 ​

这个游戏属于公平组合游戏，因为任何状态下，可以进行的移动只取决于当前状态（数字 n），而与轮到哪个玩家无关。

解决这类问题的经典方法是 P/N 分析：

  • P-position (Previous player winning)：前一个玩家（也就是对手）有必胜策略。换句话说，当前玩家处于必败态。
  • N-position (Next player winning)：下一个玩家（也就是当前玩家）有必胜策略。换句话说，当前玩家处于必胜态。

它们有以下性质：

  • 所有无法移动的最终状态都是 P-position。
  • 从 N-position 出发，至少存在一种移动可以到达 P-position。
  • 从 P-position 出发，所有移动都只能到达 N-position。

我们的解题过程，其实就是在给 n 的不同情况打上 P 或 N 的标签，喵~

2. 数论小技巧 ​

  • 奇偶性 (Parity)：奇 - 奇 = 偶，偶 - 奇 = 奇，偶 - 偶 = 偶。这个简单的性质是整个解法的基础。
  • 判断2的幂：一个正整数 n 是2的幂，当且仅当它的二进制表示中只有一个 1。一个超酷的位运算技巧是 n > 0 && (n & (n - 1)) == 0。
    • 比如 n = 8，二进制是 1000。
    • n - 1 = 7，二进制是 0111。
    • 1000 & 0111 (按位与) 的结果是 0000。
    • 这个技巧比循环除法快多啦！

好啦，今天的解题分享就到这里啦！希望本喵的讲解对主人有所帮助哦~ 如果还有其他想玩的游戏或者想解的题目，随时可以再来找我，喵！

Released under the MIT License.

Copyright © 2024-present Moe