题解 | #小红和小紫的取素因子游戏#

题目链接

题目描述

小红和小紫有一个正整数 $x$ ，她们轮流进行操作。每位玩家可以选择 $x$ 的一个素因子 $p$ ，然后将 $x$ 替换为 $x/p$ 。小红先手。当轮到某位玩家时，如果当前的数 $x=1$ ，则她无法操作，判为失败。假设两人都采取最优策略，请判断谁会获胜。

解题思路

这是一个公平组合游戏（Impartial Game），因为对于任何一个游戏状态（当前的数字 $x$ ），可行的操作集合只取决于状态本身，而与轮到哪位玩家无关。

游戏的核心操作是将 $x$ 替换为 $x/p$ 。如果我们考虑 $x$ 的质因数分解形式 $x = p_1^{a_1} \cdot p_2^{a_2} \cdot \dots \cdot p_k^{a_k}$ ，那么每次操作实际上就是将某个质因子 $p_i$ 的指数 $a_i$ 减一。

游戏结束的条件是 $x=1$ ，此时所有的质因子的指数都变为了 0。这意味着，从任意一个初始的 $x$ 开始，游戏能够进行的总步数是固定的，它等于 $x$ 的所有质因子（计入重复）的总个数，即 $\sum a_i$ 。

例如，如果 $x=12=2^2 \cdot 3^1$ ，那么总的质因子个数是 $2+1=3$ 。无论玩家如何选择（先除以2，还是先除以3），游戏都将精确地进行 3 步。

既然总步数是固定的，那么我们就可以根据总步数的奇偶性来判断胜负：

如果总步数是奇数，那么先手（小红）将进行第 1, 3, 5, ..., 最后一（奇数）步。小红走完最后一步后，数字变为 1，轮到小紫时无法操作，所以小红获胜。
如果总步数是偶数（或0），那么后手（小紫）将进行第 2, 4, 6, ..., 最后一（偶数）步。小紫走完最后一步后，数字变为 1，轮到小红时无法操作，所以小紫获胜。

因此，问题就转化为了：计算给定整数 $x$ 的总质因子数量，并判断其奇偶性。我们可以使用试除法来统计总质因子数。

代码

c++
java
python

#include <iostream>

using namespace std;

void solve() {
    long long x;
    cin >> x;
    int total_moves = 0;
    
    // 试除法统计质因子总数
    for (long long i = 2; i * i <= x; ++i) {
        while (x % i == 0) {
            total_moves++;
            x /= i;
        }
    }
    // 如果 x 最后还剩下大于 1 的数，它本身也是一个质因子
    if (x > 1) {
        total_moves++;
    }
    
    // 根据总步数奇偶性判断胜负
    if (total_moves % 2 != 0) {
        cout << "kou\n";
    } else {
        cout << "yukari\n";
    }
}

int main() {
    ios::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) {
            long x = sc.nextLong();
            int total_moves = 0;
            
            // 试除法统计质因子总数
            for (long i = 2; i * i <= x; ++i) {
                while (x % i == 0) {
                    total_moves++;
                    x /= i;
                }
            }
            // 如果 x 最后还剩下大于 1 的数，它本身也是一个质因子
            if (x > 1) {
                total_moves++;
            }
            
            // 根据总步数奇偶性判断胜负
            if (total_moves % 2 != 0) {
                System.out.println("kou");
            } else {
                System.out.println("yukari");
            }
        }
    }
}

t = int(input())
for _ in range(t):
    x = int(input())
    total_moves = 0
    
    # 试除法统计质因子总数
    i = 2
    while i * i <= x:
        while x % i == 0:
            total_moves += 1
            x //= i
        i += 1
        
    # 如果最后 x 还大于 1，说明剩下的 x 也是一个质因数
    if x > 1:
        total_moves += 1
    
    # 根据总步数奇偶性判断胜负
    if total_moves % 2 != 0:
        print("kou")
    else:
        print("yukari")

算法及复杂度

算法：博弈论 + 试除法
时间复杂度：对于每组测试数据，时间复杂度为 $O(\sqrt{x})$ 。总时间复杂度为 $O(T \cdot \sqrt{\max(x)})$ ，其中 $T$ 是游戏局数， $x$ 是给定的整数。
空间复杂度： $O(1)$ ，只需要常数空间。