「SMOI-R1」Queue

Luogu

IDLGP10405

Time1000ms

Memory512MB

DifficultyP2

有一个人数为 $n$ 的队伍，队伍中第 $i$ 个人编号为 $i$。从第一个人依次给后面的那个人传一个数，直到传到第 $n$ 个人。给后面的那个人传数的规则为： - 第一个人的数为 $1$。 - 如果这个人的编号为奇数，那么给后面的人传的数是他现在的数**按位与**上后面那个人的编号。 - 如果这个人的编号为偶数，那么给后面的人传的数是他现在的数**按位异或**上后面那个人的编号。求出传给第 $n$ 个人的数字。但是求一个的太好求了，所以你要求 $t$ 种情况的。 ## Input **本题有多组数据**。第一行一个整数 $t$，表示数据组数。对于每组数据：只有一个数 $n$，代表队伍人数。 ## Output 对于每组数据，输出一个数，代表传给第 $n$ 个人的数字。 [samples] ## Background 签到题…… ## Note ### 样例解释对于第二组数据： - 第一个人向下一个人传的数是 $1\operatorname{and}2=0$。 - 第二个人向下一个人传的数是 $0\operatorname{xor}3=3$。 - 第三个人向下一个人传的数是 $3\operatorname{and}4=0$。 - 第四个人向下一个人传的数是 $0\operatorname{xor}5=5$。所以答案是 $5$。 ### 数据范围 **本题采用捆绑测试**。 subtask 编号|$t\leq$| $n\leq$| 分值 -|-|-|- $1$|$10^2$|$10^5$|$20$ $2$|$10^6$|$10^7$|$20$ $3$|$10^6$|$10^{18}$|$60$ 对于 $100\%$ 的数据,保证 $1\le t\le10^6,1\le n\le 10^{18}$。

Samples

Input #1

Output #1

1
5
8

API Response (JSON)

{
  "problem": {
    "name": "「SMOI-R1」Queue",
    "description": {
      "content": "有一个人数为 $n$ 的队伍，队伍中第 $i$ 个人编号为 $i$。 从第一个人依次给后面的那个人传一个数，直到传到第 $n$ 个人。给后面的那个人传数的规则为： - 第一个人的数为 $1$。 - 如果这个人的编号为奇数，那么给后面的人传的数是他现在的数**按位与**上后面那个人的编号。 - 如果这个人的编号为偶数，那么给后面的人传的数是他现在的数**按位异或**上后面那个人的编号。 求出传",
      "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": "LGP10405"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一个人数为 $n$ 的队伍，队伍中第 $i$ 个人编号为 $i$。\n\n从第一个人依次给后面的那个人传一个数，直到传到第 $n$ 个人。给后面的那个人传数的规则为：\n\n- 第一个人的数为 $1$。\n- 如果这个人的编号为奇数，那么给后面的人传的数是他现在的数**按位与**上后面那个人的编号。\n- 如果这个人的编号为偶数，那么给后面的人传的数是他现在的数**按位异或**上后面那个人的编号。\n\n求出传...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments