题解 | #因数博弈#

题目链接

题目描述

Alice 和 Bob 玩一个取石子游戏，初始有 $N$ 颗石子。玩家轮流操作，Alice 先手。操作规则如下：

设当前石子数为 $x$ 。找出 $x$ 的所有真因数 $d$ 中满足 $1 < d < x$ 的因数集合 $S$ 。
如果集合 $S$ 为空，则当前玩家直接获胜。
否则，从 $S$ 中任选一个数 $p$ ，将石子数量变为 $p$ 。

双方都采取最优策略，判断谁将获胜。

解题思路

这是一个规则新颖的公平组合游戏。由于 $N$ 的范围高达 $10^{12}$ ，我们无法使用动态规划表，必须直接分析得出规律。

首先，我们分析游戏的终止和获胜条件：当轮到某个玩家时，如果当前的石子数 $x$ 的真因数集合 $S$ （不含1和x本身）为空，则该玩家获胜。一个数没有这类真因数，当且仅当这个数是质数或1。因此，游戏状态为质数或1时，轮到的玩家直接获胜，这是一个必胜态。

基于此，我们可以推导其他状态的胜负情况：

一个状态是必胜态 (W)，如果它能转移到一个必败态 (L)。
一个状态是必败态 (L)，如果它的所有转移都只能到达必胜态 (W)。

我们来分析不同类型的数：

$N$ 是质数或1: 根据规则，这是必胜态。Alice 赢。
$N = p^2$ (p是质数): $N$ 唯一的合法操作是转移到状态 $p$ 。因为 $p$ 是质数，是必胜态。由于所有（唯一的）转移都通向必胜态，所以 $N=p^2$ 是一个必败态。Bob 赢。
$N = p \cdot q$ (p, q是不同质数): $N$ 的合法操作是转移到状态 $p$ 或 $q$ 。两者都是质数，都是必胜态。因此， $N=p \cdot q$ 也是一个必败态。Bob 赢。
$N$ 有3个或更多质因数 (计算重复，例如 $p^3, pqr, p^2q$ ): 这样的数 $N$ 总可以找到一个真因数 $d$ ，而这个 $d$ 恰好由两个质因数构成（例如，从 $p^3$ 可以转移到 $p^2$ ，从 $pqr$ 可以转移到 $pq$ ）。根据我们刚才的分析，任何由两个质因数构成的数（ $p^2$ 或 $pq$ ）都是必败态。因此，任何有3个或更多质因数的数，都可以一步转移到必败态，所以它本身是一个必胜态。Alice 赢。

最终结论:

Bob 赢 (必败态): 当且仅当初始石子数 $N$ 的质因数分解中，质因数的总个数（计入重复）恰好为 2。
Alice 赢 (必胜态): 其他所有情况（质因数个数为 0, 1, 或 $\ge 3$ ）。

因此，解题算法就是对 $N$ 进行质因数分解，并统计质因数的总个数。

代码

cpp
java
python

#include <iostream>

using namespace std;

// 计算 n 的质因数个数 (包括重复)
int count_prime_factors(long long n) {
    if (n == 1) return 0;
    int count = 0;
    
    // 优化：处理因子2
    while (n % 2 == 0) {
        count++;
        n /= 2;
    }

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

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

    long long n;
    cin >> n;
    
    int factors_count = count_prime_factors(n);
    
    if (factors_count == 2) {
        cout << "Bob" << endl;
    } else {
        cout << "Alice" << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    // 计算 n 的质因数个数 (包括重复)
    public static int countPrimeFactors(long n) {
        if (n == 1) return 0;
        int count = 0;

        while (n % 2 == 0) {
            count++;
            n /= 2;
        }

        for (long i = 3; i * i <= n; i += 2) {
            while (n % i == 0) {
                count++;
                n /= i;
            }
        }

        if (n > 1) {
            count++;
        }
        
        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        
        int factorsCount = countPrimeFactors(n);
        
        if (factorsCount == 2) {
            System.out.println("Bob");
        } else {
            System.out.println("Alice");
        }
    }
}

import sys

def count_prime_factors(n):
    if n == 1:
        return 0
    
    count = 0
    while n % 2 == 0:
        count += 1
        n //= 2
    
    d = 3
    while d * d <= n:
        while n % d == 0:
            count += 1
            n //= d
        d += 2
        
    if n > 1:
        count += 1
        
    return count

def main():
    try:
        n = int(sys.stdin.readline())
        factors_count = count_prime_factors(n)
        
        if factors_count == 2:
            print("Bob")
        else:
            print("Alice")
            
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：数论、博弈论
时间复杂度：算法的核心是计算质因数的个数。通过试除法，我们只需要检查到 $\sqrt{N}$ 。因此，对于每个输入 $N$ ，时间复杂度为 $\mathcal{O}(\sqrt{N})$ 。
空间复杂度：只需要常数个变量来存储中间结果，空间复杂度为 $\mathcal{O}(1)$ 。