← 返回题目列表

AtCoder · awc0001_a

A. 细菌生长实验

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

分数: 166 分

问题陈述

高桥正在生物实验室进行细菌生长实验。

在这个实验中,细菌菌落在特殊的培养基中生长。每个群体以固定的间隔分裂,并且一个新的群体恰好具有 2 倍于原始菌落大小的诞生。

实验开始时,只有 1 菌落大小 1 在培养基中。之后,发生以下增长 K 次。

增长:对于当前存在的每个殖民地,都会诞生一个大小是该殖民地两倍的新殖民地。此时,原来的殖民地还残留下来。

换句话说,每次生长时菌落数量都会增加。然而,可能存在多个相同大小的菌落,但由于研究记录它们是按大小分类的,因此相同大小的菌落被计为 1 类型。

之后 K 已发生生长,培养基中存在多少种类型的菌落?换句话说,找到显示为现有菌落大小的不同值的数量。

约束

  • 1 \leq K \leq 10^{18}
  • K 是一个整数

输入

K
  • 第一行包含一个整数 K 代表生长数量。

输出

输出之后的菌落类型数(不同大小的数) K 单行生长。


示例输入 1

2

示例输出 1

3

示例输入 2

10

示例输出 2

11

示例输入 3

1000000000000000000

示例输出 3

1000000000000000001