20140107 - 关灯
Time Limit : 1 秒
Memory Limit : 128 MB
有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
Input
n 一个整数
Output
一个整数,即操作后所有开状态的灯编号之和。
Examples
Input
3
Output
1