#P17496. [ICPC 2026 Wuhan I] Prime Game
[ICPC 2026 Wuhan I] Prime Game
题目描述
彩叶和辉夜最近迷上了一个基于质数的博弈游戏。
起初,她们共有一个正整数 。两人将轮流进行操作,彩叶与辉夜各完成一次操作视为一个回合。在每一个回合中:
- 彩叶先手:她需要选择一个非负整数 (),并将当前的 替换为 。
- 辉夜后手:她需要选择一个能整除当前 的质数 (即 ),并将当前的 替换为 。
以上操作会不断重复,直到某个回合结束后,若 ,则游戏立即结束。
在游戏过程中,彩叶希望最大化游戏进行的总回合数,而辉夜希望最小化总回合数。假设双方都足够聪明并采取最优策略,请你求出游戏最终会进行多少个回合。
输入格式
第一行包含一个整数 (),表示游戏初始的数字。
输出格式
输出一行包含一个整数,表示在双方都采取最优策略的情况下,游戏最终进行的总回合数。
1
0
9
4
16
5