20140107 - 关灯

有n个灯(1≤n≤1000000000),编号为1,2,……n,同时有n个人,依次对灯进行操作。

开始时,所有灯是关闭状态。

第1人操作:将所有灯打开

第2人操作:将2及2的倍数的灯,状态取反,即开状态变为关状态,其状态变为开状态。

第3人操作:将3及3倍数的灯状态取反。

……

第i人操作:将i及i的倍数的灯状态取反(1≤i≤n),当所有操作完成之后,计算出所有开状态灯的编号之和。

例如:n=6, 0—关状态,1—开状态

开始 0 0 0 0 0 0

第1人操作之后:变成 1 1 1 1 1 1

第2人操作之后:变成 1 0 1 0 1 0

第3人操作之后:变成 1 0 0 0 1 1

第4人操作之后:变成 1 0 0 1 1 1

第5人操作之后:变成 1 0 0 1 0 1

第6人操作之后:变成 1 0 0 1 0 0

所有开状态灯编号之和为 1+4=5

输入

n 一个整数

输出

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

样例

输入

3

输出

1
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题