[信息与未来 2014] 关灯

Luogu
IDLGB4134
Time1000ms
Memory512MB
DifficultyP2
数学2014江苏信息与未来
有 $n$ 盏灯,编号为 $1,2,\cdots,n$,同时有 $n$ 个人,依次对灯进行操作。开始时,所有的灯都是关闭状态: - 第 $1$ 个人的操作:将所有灯打开; - 第 $2$ 个人的操作:将 $2$ 及 $2$ 的倍数的灯,状态取反(即“开”状态变为“关”状态,“关”状态变为“开”状态); - 第 $3$ 个人的操作:将 $3$ 及 $3$ 倍数的灯状态取反; - …… - 第 $i(1\le i\le n)$ 个人的操作:将 $i$ 及 $i$ 倍数的灯状态取反。 当所有操作完成之后,计算出所有开状态灯的编号之和。 ## Input 一个整数,表示 $n$。 ## Output 一个整数,即操作后所有开状态的灯的编号之和。 [samples] ## Note ### 样例解释 `0` 表示关状态,`1` 表示开状态: - 开始:`000000` - 第 $1$ 人操作之后,变成:`111111` - 第 $2$ 人操作之后,变成:`101010` - 第 $3$ 人操作之后,变成:`100011` - 第 $4$ 人操作之后,变成:`100111` - 第 $5$ 人操作之后,变成:`100101` - 第 $6$ 人操作之后,变成:`100100` 则所有开状态灯的编号之和为:$1+4=5$。 ### 数据范围 $1\le n\le 10^9$。
Samples
Input #1
6
Output #1
5
API Response (JSON)
{
  "problem": {
    "name": "[信息与未来 2014] 关灯",
    "description": {
      "content": "有 $n$ 盏灯,编号为 $1,2,\\cdots,n$,同时有 $n$ 个人,依次对灯进行操作。开始时,所有的灯都是关闭状态: - 第 $1$ 个人的操作:将所有灯打开; - 第 $2$ 个人的操作:将 $2$ 及 $2$ 的倍数的灯,状态取反(即“开”状态变为“关”状态,“关”状态变为“开”状态); - 第 $3$ 个人的操作:将 $3$ 及 $3$ 倍数的灯状态取反; - …… - 第 $i(",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4134"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 盏灯,编号为 $1,2,\\cdots,n$,同时有 $n$ 个人,依次对灯进行操作。开始时,所有的灯都是关闭状态:\n- 第 $1$ 个人的操作:将所有灯打开;\n- 第 $2$ 个人的操作:将 $2$ 及 $2$ 的倍数的灯,状态取反(即“开”状态变为“关”状态,“关”状态变为“开”状态);\n- 第 $3$ 个人的操作:将 $3$ 及 $3$ 倍数的灯状态取反;\n- ……\n- 第 $i(...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments