开始 2021-05-12 00:00:00

2014 年江苏省信息与未来夏令营

结束 2022-05-12 00:00:00
Contest is over.
当前 2024-11-28 11:37:47

F. 关灯

描述

有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

Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交