J. Even Numbers

Codeforces

IDCF10197J

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Yousef loves playing with functions in his free time. Today, he invents the following function: Yousef will give you a list of queries, and you need to find the answers for them. For each query, you are given an integer n, and your task is to count the number of integers m in which (0 ≤ m ≤ n) and calc(n, m) is an even number. Can you? The first line contains an integer T (1 ≤ T ≤ 105) specifying the number of test cases. Each test case consists of a single line containing an integer n (0 ≤ n ≤ 1018), as described in the problem statement above. For each test case, print a single line containing the number of integers m in which (0 ≤ m ≤ n) and calc(n, m) is an even number. ## Input The first line contains an integer T (1 ≤ T ≤ 105) specifying the number of test cases.Each test case consists of a single line containing an integer n (0 ≤ n ≤ 1018), as described in the problem statement above. ## Output For each test case, print a single line containing the number of integers m in which (0 ≤ m ≤ n) and calc(n, m) is an even number. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ n \in \mathbb{Z} $ with $ 0 \leq n \leq 10^{18} $. Let $ \text{calc}(n, m) = \binom{n}{m} $, the binomial coefficient. **Constraints** 1. $ 1 \leq T \leq 10^5 $ 2. For each test case: $ 0 \leq n \leq 10^{18} $ 3. $ m \in \mathbb{Z} $, $ 0 \leq m \leq n $ **Objective** For each test case, compute: $$ \left| \left\{ m \in \mathbb{Z} \mid 0 \leq m \leq n \text{ and } \binom{n}{m} \equiv 0 \pmod{2} \right\} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "J. Even Numbers",
    "description": {
      "content": "Yousef loves playing with functions in his free time. Today, he invents the following function: Yousef will give you a list of queries, and you need to find the answers for them. For each query, you ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10197J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Yousef loves playing with functions in his free time. Today, he invents the following function:\n\nYousef will give you a list of queries, and you need to find the answers for them. For each query, you ...",
      "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, let $ n \\in \\mathbb{Z} $ with $ 0 \\leq n \\leq 10^{18} $.  \nLet $ \\text{calc}(n, m) = \\binom{n}{m} $, the b...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments