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$。