B4134 [信息与未来 2014] 关灯

题目描述

有 $n$ 盏灯,编号为 $1,2,\cdots,n$,同时有 $n$ 个人,依次对灯进行操作。开始时,所有的灯都是关闭状态: - 第 $1$ 个人的操作:将所有灯打开; - 第 $2$ 个人的操作:将 $2$ 及 $2$ 的倍数的灯,状态取反(即“开”状态变为“关”状态,“关”状态变为“开”状态); - 第 $3$ 个人的操作:将 $3$ 及 $3$ 倍数的灯状态取反; - …… - 第 $i(1\le i\le n)$ 个人的操作:将 $i$ 及 $i$ 倍数的灯状态取反。 当所有操作完成之后,计算出所有开状态灯的编号之和。

输入格式

一个整数,表示 $n$。

输出格式

一个整数,即操作后所有开状态的灯的编号之和。

说明/提示

### 样例解释 `0` 表示关状态,`1` 表示开状态: - 开始:`000000` - 第 $1$ 人操作之后,变成:`111111` - 第 $2$ 人操作之后,变成:`101010` - 第 $3$ 人操作之后,变成:`100011` - 第 $4$ 人操作之后,变成:`100111` - 第 $5$ 人操作之后,变成:`100101` - 第 $6$ 人操作之后,变成:`100100` 则所有开状态灯的编号之和为:$1+4=5$。 ### 数据范围 $1\le n\le 10^9$。