33OJ
登录 注册

#P17496. [ICPC 2026 Wuhan I] Prime Game

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

[ICPC 2026 Wuhan I] Prime Game

Problem Description

Iroha and Kaguya have recently become fascinated by a mathematical game based on integers.

Initially, they share a positive integer nn. The two players take turns performing operations; a single round is defined as both Iroha and Kaguya completing one operation each. In each round:

  1. Iroha goes first: She must choose a non-negative integer xx (0≤x<n0 \le x<n) and replace the current nn with n+xn+x.
  2. Kaguya goes second: She must choose a prime number pp that divides the current nn (i.e., p∣np\mid n) and replace the current nn with np\frac{n}{p}.

The above operations repeat continuously. If n=1n=1 after the end of any round, the game ends immediately.

During the game, Iroha aims to maximize the total number of rounds played, while Kaguya aims to minimize the total number of rounds. Assuming both players are perfectly rational and adopt optimal strategies, please determine the total number of rounds the game will ultimately last.

Input Format

The first line contains an integer nn (1≤n≤10181 \le n \le 10^{18}), representing the initial number of the game.

Output Format

Output a single line containing an integer, representing the total number of rounds the game will last given that both players play optimally.

1
0
9
4
16
5