数字游戏中先手胜负判断及最小制胜数字求解的 C++ 实现

以下是解决该问题的 C++ 代码： ```cpp #include <iostream> #include <vector> #include <algorithm> // 找出一个数的所有非 1 和它本身的因数 std::vector<int> findFactors(int num) { std::vector<int> factors; for (int i = 2; i * i <= num; ++i) { if (num % i == 0) { factors.push_back(i); if (i != num / i) { factors.push_back(num / i); } } } std::sort(factors.begin(), factors.end()); return factors; } // 判断先手是否能胜利，并找出第一次写出的可以制胜的最小数字 std::pair<int, int> canWin(int Q) { std::vector<int> factors = findFactors(Q); if (factors.empty()) { return {1, 0}; } for (int factor : factors) { std::vector<int> subFactors = findFactors(factor); if (subFactors.empty()) { return {1, factor}; } } return {2, 0}; } int main() { int Q; std::cin >> Q; auto result = canWin(Q); std::cout << result.first << std::endl; if (result.first == 1) { std::cout << result.second << std::endl; } return 0; } ``` ### 代码解释 1. **`findFactors` 函数**：该函数用于找出一个数的所有非 1 和它本身的因数。通过遍历从 2 到该数的平方根的所有数，若能整除该数，则将其作为因数添加到向量中，同时若该因数与商不相等，也将商添加到向量中。最后对向量进行排序。 2. **`canWin` 函数**：该函数用于判断先手是否能胜利，并找出第一次写出的可以制胜的最小数字。首先调用 `findFactors` 函数找出给定数字的所有非 1 和它本身的因数。若没有因数，则先手胜利，第一次写出的数字为 0。然后遍历这些因数，对于每个因数，再次调用 `findFactors` 函数找出其非 1 和它本身的因数。若某个因数没有非 1 和它本身的因数，则先手可以选择该因数，从而胜利。 3. **`main` 函数**：读取输入的数字 `Q`，调用 `canWin` 函数得到结果，并输出结果。 ### 复杂度分析 - **时间复杂度**：$O(\sqrt{Q})$，主要用于找出因数。 - **空间复杂度**：$O(\sqrt{Q})$，主要用于存储因数。 ######[AI问答 | 658点数解答 | 2026-03-22 20:27:16]