L. Chance

Codeforces

IDCF10108L

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

After Noura's brother, Tamim, finished his junior training, coach Fegla was impressed with his progress. He told Noura that if Tamim would solve the following problem in SCPC2015 and yet does not qualify to the ACPC2015, he will give him a chance to participate unofficially in it. The problem goes as follows: Given L and R, how many integers between them have a prime number of ones in their binary representation? Can you help Tamim participate in the ACPC2015? The first line of input contains an integer T (1 ≤ T ≤ 105), the number of test cases. Each test case will consist of two space - separated integers: L and R (0 ≤ L ≤ R ≤ 105). For each test case, print the number of integers between L and R that have a prime number of ones in their binary representation. Warning: large Input/Output data, be careful with certain languages. ## Input The first line of input contains an integer T (1 ≤ T ≤ 105), the number of test cases.Each test case will consist of two space - separated integers: L and R (0 ≤ L ≤ R ≤ 105). ## Output For each test case, print the number of integers between L and R that have a prime number of ones in their binary representation. [samples] ## Note Warning: large Input/Output data, be careful with certain languages.

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $, let $ L_k, R_k \in \mathbb{Z} $ satisfy $ 0 \leq L_k \leq R_k \leq 10^5 $. Let $ \text{popcount}(n) $ denote the number of 1-bits in the binary representation of $ n \in \mathbb{Z}_{\geq 0} $. Let $ \mathbb{P} $ denote the set of prime numbers. **Constraints** 1. $ 1 \leq T \leq 10^5 $ 2. For each $ k \in \{1, \dots, T\} $: $ 0 \leq L_k \leq R_k \leq 10^5 $ **Objective** For each test case $ k $, compute: $$ \left| \left\{ n \in \mathbb{Z} \mid L_k \leq n \leq R_k \text{ and } \text{popcount}(n) \in \mathbb{P} \right\} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "L. Chance",
    "description": {
      "content": "After Noura's brother, Tamim, finished his junior training, coach Fegla was impressed with his progress. He told Noura that if Tamim would solve the following problem in SCPC2015 and yet does not qual",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10108L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "After Noura's brother, Tamim, finished his junior training, coach Fegla was impressed with his progress. He told Noura that if Tamim would solve the following problem in SCPC2015 and yet does not qual...",
      "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 $ L_k, R_k \\in \\mathbb{Z} $ satisfy $ 0 \\leq L_k \\leq R_k \\leq 10^5 $.  \nLet...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments