首页 > 试题广场 >

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

[编程题]小红和小紫的取素因子游戏

热度指数：1506 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 小红和小紫手中有一个正整数 $x$ 。她们轮流进行如下操作：
${\hspace{20pt}}_\texttt{1.}\,$ 选择 $x$ 的一个素因子 $k\left(k>1\right)$ ；
${\hspace{20pt}}_\texttt{2.}\,$ 将 $x$ 替换为 $\tfrac{x}{k}$ 。
$\hspace{15pt}$ 小红先手；若某位玩家无法进行操作，则她立即失败。两人都足够聪明，请你判断每局游戏的最终赢家。游戏共进行 $t$ 局，每局的初始整数可能不同。

$\hspace{15pt}$ 【名词解释】
$\hspace{23pt}\bullet\,$ 素因子：若正整数 $k$ 是质数，且 $k$ 能整除正整数 $x$ ，则称 $k$ 为 $x$ 的素因子。

输入描述:

第一行输入一个整数 ，表示游戏的局数。 
此后  行，每行输入一个整数 ，表示该局游戏的初始整数。

输出描述:

对于每局游戏，在一行上输出一个字符串： 
若小红最终获胜，输出 ； 
若小紫最终获胜，输出 。 
大小写需与上述格式完全一致。

示例1

输入

2
5
12

输出

kou
kou

说明

在此样例中，共有  局游戏： 
第  局：，唯一的素因子为 。小红选择 ，得到 ；此时小紫无法继续操作，小红获胜； 
第  局：，一次可能的最优操作序列为 ，共进行  次操作（奇数次），因此先手的小红获胜。

示例2

输入

输出

yukari
yukari
kou

算法知识视频讲解

Java

BraveCoder

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); 

        while (n-- > 0) {
            int x = sc.nextInt();
            int count = 0;

            // 质因数分解：从最小质数2开始检查
            // 循环条件i*i <= x：减少不必要的检查，优化效率
            for (int i = 2; i * i <= x; i++) {
                // 若i是x的质因数，统计其出现次数
                while (x % i == 0) {
                    x = x / i; // 除去所有当前质因数i
                    count++; 
                }
            }

            // 若剩余x大于1，说明x本身是一个质因数
            if (x > 1) {
                count++;
            }

            // 根据质因数总个数的奇偶性输出结果
            if (count % 2 == 1) {
                System.out.println("kou");
            } else {
                System.out.println("yukari");
            }
        }
        sc.close();
    }
}

发表于 2025-09-06 18:13:30 回复(0)