首页 > 试题广场 >

因数博弈

[编程题]因数博弈
  • 热度指数：107 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}Alice 和 Bob 正在用神奇的数学魔法玩一个取石子游戏。

\hspace{15pt}有 n 个石子堆在一起，Alice 和 Bob 轮流进行操作，每次操作的流程如下：

{\hspace{20pt}}_\texttt{1.}\,设此时剩下的石子个数为 x，求出集合 S = \{d \in N^*∣\left( d∣x \right)∧\left( 1<d<x \right)\}。若集合 S 为空，则立即 赢得 这场游戏。
{\hspace{20pt}}_\texttt{2.}\,从集合 S 中任选一个数 p，并动用神奇的数学魔法将石子的数量变为 p。

\hspace{15pt}Alice 想知道，如果自己先手，且自己和 Bob 都采取最优策略，最终谁能获胜？

输入描述:
\hspace{15pt}输入一行一个正整数 n ( 1 \leqq n \leqq 10^{12} )，表示初始时石子的个数。


输出描述:
\hspace{15pt}如果 Alice 在最优策略下能够赢得游戏，请输出 \texttt{Alice}；否则输出 \texttt{Bob}。
示例1

输入

6

输出

Bob
示例2

输入

30

输出

Alice
示例3

输入

1

输出

Alice
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-02 10:28:23
题目链接 因数博弈 题目描述 Alice 和 Bob 玩一个取石子游戏，初始有 颗石子。玩家轮流操作，Alice 先手。 操作规则如下： 设当前石子数为 。找出 的所有真因数 中满足 的因数集合 。 如果集合 为空，则当前玩家直接获胜。 否则，从 中任选一个数 ，将石子数量变为 。 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客242693846号
发表于 2025-08-06 16:44:34
观察出来的，将这个数进行质因数分解。如果分解出来的数量是2个，例如4=2*2,6=2*3。那么就是Bob获胜，其余情况则是Alice获胜。 def prime_factors(n): factors = [] x = n i = 2 while i * i <= 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
1条回答 13浏览

热门推荐

相关试题

因数博弈

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号