B. Xor Sums

Codeforces

IDCF10240B

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Diego knows that the sum of all integers between $1$ and $N$ is $frac(N (N + 1), 2)$. However, he is wondering how to compute the exclusive or of all integers between $1$ and $N$. Exclusive or is also known as xor. Most programming languages represent it with the character _^_. First, a single integer, $T$ $(1 <= T <= 10^5)$: the number of test cases. Then $T$ lines, each of which contains a single integer, $N$ $(1 <= N <= 10^(18))$. For each test case output a line containing a single integer: the exclusive or of every number between $1$ and $N$. ## Input First, a single integer, $T$ $(1 <= T <= 10^5)$: the number of test cases.Then $T$ lines, each of which contains a single integer, $N$ $(1 <= N <= 10^(18))$. ## Output For each test case output a line containing a single integer: the exclusive or of every number between $1$ and $N$. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $, let $ N_k \in \mathbb{Z} $ be a positive integer. **Constraints** 1. $ 1 \le T \le 10^5 $ 2. For each $ k $, $ 1 \le N_k \le 10^{18} $ **Objective** For each test case $ k $, compute: $$ X_k = \bigoplus_{i=1}^{N_k} i $$ where $ \oplus $ denotes the bitwise XOR operation.

API Response (JSON)

{
  "problem": {
    "name": "B. Xor Sums",
    "description": {
      "content": "Diego knows that the sum of all integers between $1$ and $N$ is $frac(N (N + 1), 2)$. However, he is wondering how to compute the exclusive or of all integers between $1$ and $N$. Exclusive or is als",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10240B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Diego knows that the sum of all integers between $1$ and $N$ is $frac(N (N + 1), 2)$. However, he is wondering how to compute the exclusive or of all integers between $1$ and $N$.\n\nExclusive or is als...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ N_k \\in \\mathbb{Z} $ be a positive integer.\n\n**Constraints**  \n1. $ 1 \\le ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments