Score: $300$ points

问题描述

在黑板上写有一个整数 $N$。

Takahashi 将重复以下一系列操作，直到黑板上所有不小于 $2$ 的整数都被移除：

• 选择一个黑板上书写的不小于 $2$ 的整数 $x$。
• 从黑板上擦去一个出现的 $x$。然后，在黑板上写下两个新的整数 $\left \lfloor \dfrac{x}{2} \right\rfloor$ 和 $\left\lceil \dfrac{x}{2} \right\rceil$。
• Takahashi 执行这一系列操作需要支付 $x$ 日元。

其中，$\lfloor a \rfloor$ 表示不大于 $a$ 的最大整数，而 $\lceil a \rceil$ 表示不小于 $a$ 的最小整数。

当无法再进行操作时，Takahashi 累计支付的总金额是多少？ 可以证明，无论操作的顺序如何，他将支付的总额是一个常数。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a single integer $N$ written on a blackboard.
Takahashi will repeat the following series of operations until all integers not less than $2$ are removed from the blackboard:

• Choose one integer $x$ not less than $2$ written on the blackboard.
• Erase one occurrence of $x$ from the blackboard. Then, write two new integers $\left \lfloor \dfrac{x}{2} \right\rfloor$ and $\left\lceil \dfrac{x}{2} \right\rceil$ on the blackboard.
• Takahashi must pay $x$ yen to perform this series of operations.

Here, $\lfloor a \rfloor$ denotes the largest integer not greater than $a$, and $\lceil a \rceil$ denotes the smallest integer not less than $a$.

What is the total amount of money Takahashi will have paid when no more operations can be performed?
It can be proved that the total amount he will pay is constant regardless of the order in which the operations are performed.

Constraints

• $2 \leq N \leq 10^{17}$

Input

The input is given from Standard Input in the following format:

$N$

Output

Print the total amount of money Takahashi will have paid, in yen.

Sample Input 1

3

Sample Output 1

5

Here is an example of how Takahashi performs the operations:

• Initially, there is one $3$ written on the blackboard.
• He chooses $3$. He pays $3$ yen, erases one $3$ from the blackboard, and writes $\left \lfloor \dfrac{3}{2} \right\rfloor = 1$ and $\left\lceil \dfrac{3}{2} \right\rceil = 2$ on the blackboard.
• There is one $2$ and one $1$ written on the blackboard.
• He chooses $2$. He pays $2$ yen, erases one $2$ from the blackboard, and writes $\left \lfloor \dfrac{2}{2} \right\rfloor = 1$ and $\left\lceil \dfrac{2}{2} \right\rceil = 1$ on the blackboard.
• There are three $1$s written on the blackboard.
• Since all integers not less than $2$ have been removed from the blackboard, the process is finished.

Takahashi has paid a total of $3 + 2 = 5$ yen for the entire process, so print $5$.

Sample Input 2

340

Sample Output 2

2888

Sample Input 3

100000000000000000

Sample Output 3

5655884811924144128

update @ 2024/3/10 01:32:47