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

思路

经典博弈论问题。小红和小紫轮流对正整数 x 操作：每次选一个 x 的素因子 k（k > 1），把 x 变成 x/k。谁先没法操作谁就输，小红先手。

关键观察：不管怎么选素因子，总操作次数是固定的，等于 x 的素因子个数（含重复）。

为什么？每次操作都是把 x 除以它的某个素因子，也就是从 x 的质因数分解里去掉一个素因子。不管你每次选哪个素因子去掉，最终都要把所有素因子去完才会变成 1。所以总步数 = x 的质因数分解中素因子的总个数（计重数）。

比如 x = 12 = 2^2 * 3，一共 3 个素因子（两个 2 和一个 3），不管怎么操作都是 3 步。

有了这个结论就简单了：

  • 总步数为奇数：先手（小红）赢，输出 kou
  • 总步数为偶数：后手（小紫）赢，输出 yukari
  • 特别地，x = 1 时步数为 0（偶数），小红直接没法操作，输出 yukari

做法就是对每个 x 做质因数分解，数一下素因子总个数，判奇偶即可。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        long long x;
        scanf("%lld", &x);
        int cnt = 0;
        for (long long i = 2; i * i <= x; i++) {
            while (x % i == 0) {
                cnt++;
                x /= i;
            }
        }
        if (x > 1) cnt++;
        puts(cnt % 2 == 1 ? "kou" : "yukari");
    }
    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();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            long x = sc.nextLong();
            int cnt = 0;
            for (long i = 2; i * i <= x; i++) {
                while (x % i == 0) {
                    cnt++;
                    x /= i;
                }
            }
            if (x > 1) cnt++;
            sb.append(cnt % 2 == 1 ? "kou" : "yukari").append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    out = []
    for _ in range(t):
        x = int(input())
        cnt = 0
        i = 2
        while i * i <= x:
            while x % i == 0:
                cnt += 1
                x //= i
            i += 1
        if x > 1:
            cnt += 1
        out.append("kou" if cnt % 2 == 1 else "yukari")
    print('\n'.join(out))

solve()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let idx = 0;
    const t = parseInt(lines[idx++]);
    const out = [];
    for (let i = 0; i < t; i++) {
        let x = BigInt(lines[idx++].trim());
        let cnt = 0;
        for (let d = 2n; d * d <= x; d++) {
            while (x % d === 0n) {
                cnt++;
                x /= d;
            }
        }
        if (x > 1n) cnt++;
        out.push(cnt % 2 === 1 ? "kou" : "yukari");
    }
    console.log(out.join('\n'));
});

复杂度分析

  • 时间复杂度: ，每组数据做一次试除法分解质因数。
  • 空间复杂度: ，只用了常数额外空间。

小结

这题的核心洞察是：每次操作恰好消耗一个素因子，所以不管双方怎么选，总操作步数等于 x 的质因数分解中素因子的总个数（计重数），是一个定值。博弈的胜负完全由这个数的奇偶性决定。看到这类"两人轮流操作、操作次数有上界"的博弈题，第一反应就是去找不变量——总步数是否固定，固定的话判奇偶就行。