题目链接

HIGH5 小红和小紫的取素因子游戏

题目描述

小红（kou）和小紫（yukari）在玩一个游戏。她们有一个正整数 x，两人轮流操作。小红先手。 每次操作，当前玩家需要选择 x 的一个质因子 p，然后将 x 替换为 x / p。 当一个玩家无法操作时（此时 x 变为 1），该玩家输掉游戏。 假设两人都足够聪明，采取最优策略，请问谁会获胜？

解题思路

这是一个典型的公平博弈游戏（Impartial Game），因为在任何状态下，可以执行的操作只取决于当前的状态（数字 x），而与轮到哪位玩家无关。

这类问题的关键在于分析游戏的总步数。

  1. 游戏的核心：每次操作都是将 x 除以其一个质因子。这等价于从 x 的所有质因子（包含重复的）集合中拿走一个。

  2. 游戏结束的条件：当 x 变为 1 时，游戏结束，因为 1 没有任何质因子。

  3. 总步数是固定的：无论每次选择哪个质因子，游戏都会在固定的步数后结束。这个总步数等于 x 的质因子总数（计入重复的）。例如，对于 x = 12 = 2 * 2 * 3，质因子有 2, 2, 3 共三个。无论先除以2还是3，游戏都将进行恰好 3 步。

    • 12 -> 6 -> 3 -> 1 (3步)
    • 12 -> 4 -> 2 -> 1 (3步)

  4. 胜负判断：既然总步数是固定的，设为 k，问题就变得非常简单了：

    • 小红先手。她走第 1, 3, 5, ... 步。
    • 小紫后手。她走第 2, 4, 6, ... 步。
    • 如果总步数 k 是奇数，那么最后一步（第 k 步）必然是由小红走的。小红走完后，x 变为 1，轮到小紫时无法操作，所以小红获胜。
    • 如果总步数 k 是偶数，那么最后一步（第 k 步）必然是由小紫走的。小紫走完后，x 变为 1，轮到小红时无法操作，所以小紫获胜。

  5. 算法实现：问题就转化为了求解一个数 x 的质因子总数 k，然后判断 k 的奇偶性。

    • 我们可以用和上一题“分解质因数”类似的试除法来计算 k。
    • 遍历 i 从 2 到 sqrt(x)，每次发现 x 能被 i 整除，就计数加一，并更新 x。
    • 最后，如果 x 还不为 1，说明它本身也是一个质因子，计数再加一。

代码

#include <iostream>

using namespace std;

void solve() {
    long long x;
    cin >> x;

    long long count = 0;
    for (long long i = 2; i * i <= x; ++i) {
        while (x % i == 0) {
            count++;
            x /= i;
        }
    }
    if (x > 1) {
        count++;
    }

    if (count % 2 != 0) {
        cout << "kou" << endl;
    } else {
        cout << "yukari" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        long x = sc.nextLong();
        long count = 0;

        for (long i = 2; i * i <= x; i++) {
            while (x % i == 0) {
                count++;
                x /= i;
            }
        }
        if (x > 1) {
            count++;
        }

        if (count % 2 != 0) {
            System.out.println("kou");
        } else {
            System.out.println("yukari");
        }
    }
}

t = int(input())
for _ in range(t):
    x = int(input())
    
    count = 0
    i = 2
    while i * i <= x:
        while x % i == 0:
            count += 1
            x //= i
        i += 1
    
    if x > 1:
        count += 1
        
    if count % 2 != 0:
        print("kou")
    else:
        print("yukari")

算法及复杂度

  • 算法：博弈论、质因数分解
  • 时间复杂度：。其中 T 是测试用例的数量。对于每个 x，我们需要运行一次试除法，其复杂度为 。
  • 空间复杂度：。我们只需要常数级别的额外空间来存储变量。