AT_abc340_c [ABC340C] Divide and Divide

题目描述

黑板上写有一个整数 $N$。
高桥君会不断重复以下一系列操作，直到黑板上所有大于等于 $2$ 的整数都消失为止。

• 从黑板上写着的所有大于等于 $2$ 的整数中任选一个，记为 $x$。
• 从黑板上擦去一个 $x$，然后在黑板上新写上两个整数 $\left\lfloor \dfrac{x}{2} \right\rfloor$ 和 $\left\lceil \dfrac{x}{2} \right\rceil$。
• 每进行一次上述操作，高桥君需要支付 $x$ 日元。

这里，$\lfloor a \rfloor$ 表示不超过 $a$ 的最大整数，$\lceil a \rceil$ 表示不小于 $a$ 的最小整数。

当无法再进行操作时，高桥君支付的金额总和是多少？
另外，可以证明，无论操作顺序如何，高桥君支付的金额总和都是相同的。

输入格式

输入通过标准输入按以下格式给出。

$N$

输出格式

输出高桥君支付的金额总和。

输入输出样例 #1

输入 #1

3

输出 #1

5

输入输出样例 #2

输入 #2

340

输出 #2

2888

输入输出样例 #3

输入 #3

100000000000000000

输出 #3

5655884811924144128

说明/提示

限制条件

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

样例解释 1

高桥君进行操作的一种例子如下：

• 起初，黑板上写着一个 $3$。
• 高桥君选择 $3$，支付 $3$ 日元，将黑板上的 $3$ 擦去，写上 $\left\lfloor \dfrac{3}{2} \right\rfloor = 1$ 和 $\left\lceil \dfrac{3}{2} \right\rceil = 2$。
• 此时黑板上有一个 $2$ 和一个 $1$。
• 高桥君选择 $2$，支付 $2$ 日元，将黑板上的 $2$ 擦去，写上 $\left\lfloor \dfrac{2}{2} \right\rfloor = 1$ 和 $\left\lceil \dfrac{2}{2} \right\rceil = 1$。
• 此时黑板上有三个 $1$。
• 黑板上已没有大于等于 $2$ 的整数，操作结束。

整个过程中高桥君共支付了 $3 + 2 = 5$ 日元，因此输出 $5$。

由 ChatGPT 4.1 翻译