#B4134. [信息与未来 2014] 关灯

[信息与未来 2014] 关灯

题目描述

nn 盏灯,编号为 1,2,,n1,2,\cdots,n,同时有 nn 个人,依次对灯进行操作。开始时,所有的灯都是关闭状态:

  • 11 个人的操作:将所有灯打开;
  • 22 个人的操作:将 2222 的倍数的灯,状态取反(即“开”状态变为“关”状态,“关”状态变为“开”状态);
  • 33 个人的操作:将 3333 倍数的灯状态取反;
  • ……
  • i(1in)i(1\le i\le n) 个人的操作:将 iiii 倍数的灯状态取反。

当所有操作完成之后,计算出所有开状态灯的编号之和。

输入格式

一个整数,表示 nn

输出格式

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

6
5

提示

样例解释

0 表示关状态,1 表示开状态:

  • 开始:000000
  • 11 人操作之后,变成:111111
  • 22 人操作之后,变成:101010
  • 33 人操作之后,变成:100011
  • 44 人操作之后,变成:100111
  • 55 人操作之后,变成:100101
  • 66 人操作之后,变成:100100

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

数据范围

1n1091\le n\le 10^9