← 返回题目列表

AtCoder · abc340_c

E. 分而分之

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有一个整数 N 写在黑板上。
Takahashi会重复以下一系列操作,直到所有不小于的整数 2 从黑板上删除:

  • 选择一个整数 黑板上写着 x 不小于 2 。
  • 删除 1 个出现的 黑板上的 x 。然后,写入两个新整数 黑板上的 \left \lfloor \dfrac{x}{2} \right\rfloor 和 \left\lceil \dfrac{x}{2} \right\rceil 。
  • 高桥必须支付 x 日元执行这一系列操作。

在这里, \lfloor a \rfloor 表示不大于的最大整数 a,和 \lceil a \rceil 表示不小于的最小整数 a.

当无法进行更多操作时,高桥将支付的总金额是多少?
可以证明,无论操作执行的顺序如何,他将支付的总金额都是恒定的。

约束

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

输入

输入由标准输入按以下格式给出:

N

输出

打印高桥将支付的总金额(以日元为单位)。


示例输入 1

3

示例输出 1

5

以下是 Takahashi 如何执行操作的示例:

  • 最初,有一个 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.


示例输入 2

340

示例输出 2

2888

示例输入 3

100000000000000000

示例输出 3

5655884811924144128