← 返回题目列表

AtCoder · awc0046_b

B. 整理储物柜

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

分数: 333 分

问题陈述

高桥负责管理 N 学校体育馆的储物柜。储物柜编号为 1 to N。最初,所有储物柜都关闭。

高桥将表演 N 操作。在 i第一次操作 (i = 1, 2, \ldots, N),对于每个编号为以下倍数的储物柜 i (包括储物柜号码 i 本身),他切换其状态:如果它打开,他将其关闭,如果它关闭,他将其打开。

例如,在第一个操作中,他切换了所有编号为以下倍数的储物柜的状态 1,即储物柜 1, 2, \ldots, N。在第二次操作中,他切换了数量为以下倍数的储物柜的状态 2 最多 N,即储物柜 2, 4, 6, \ldots。在第三次操作中,他切换了数量为以下倍数的储物柜的状态 3 最多 N,即储物柜 3, 6, 9, \ldots.

所有操作完成后,找到打开的储物柜数量。

约束

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

输入

N

一个整数 N 表示储物柜的数量,在一行中给出。

输出

打印所有操作完成后打开的储物柜数量,作为单行整数。


示例输入 1

10

示例输出 1

3

示例输入 2

100

示例输出 2

10

示例输入 3

1000000000000000000

示例输出 3

1000000000