33OJ
登录 注册

#P17496. [ICPC 2026 Wuhan I] Prime Game

    ID: 20224 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>数学博弈论ICPC2026省赛/邀请赛湖北

[ICPC 2026 Wuhan I] Prime Game

题目描述

彩叶和辉夜最近迷上了一个基于质数的博弈游戏。

起初,她们共有一个正整数 nn。两人将轮流进行操作,彩叶与辉夜各完成一次操作视为一个回合。在每一个回合中:

  1. 彩叶先手:她需要选择一个非负整数 xx(0≤x<n0 \le x<n),并将当前的 nn 替换为 n+xn+x。
  2. 辉夜后手:她需要选择一个能整除当前 nn 的质数 pp(即 p∣np\mid n),并将当前的 nn 替换为 np\frac{n}{p}。

以上操作会不断重复,直到某个回合结束后,若 n=1n=1,则游戏立即结束。

在游戏过程中,彩叶希望最大化游戏进行的总回合数,而辉夜希望最小化总回合数。假设双方都足够聪明并采取最优策略,请你求出游戏最终会进行多少个回合。

输入格式

第一行包含一个整数 nn(1≤n≤10181 \le n \le 10^{18}),表示游戏初始的数字。

输出格式

输出一行包含一个整数,表示在双方都采取最优策略的情况下,游戏最终进行的总回合数。

1
0
9
4
16
5