B. Recursive Queries

Codeforces

IDCF932B

Time2000ms

Memory256MB

Difficulty—

binary searchdata structuresdfs and similar

English · Original

Chinese · Translation

Formal · Original

Let us define two functions _f_ and _g_ on positive integer numbers. You need to process _Q_ queries. In each query, you will be given three integers _l_, _r_ and _k_. You need to print the number of integers _x_ between _l_ and _r_ inclusive, such that _g_(_x_) = _k_. ## Input The first line of the input contains an integer _Q_ (1 ≤ _Q_ ≤ 2 × 105) representing the number of queries. _Q_ lines follow, each of which contains 3 integers _l_, _r_ and _k_ (1 ≤ _l_ ≤ _r_ ≤ 106, 1 ≤ _k_ ≤ 9). ## Output For each query, print a single line containing the answer for that query. [samples] ## Note In the first example: * _g_(33) = 9 as _g_(33) = _g_(3 × 3) = _g_(9) = 9 * _g_(47) = _g_(48) = _g_(60) = _g_(61) = 6 * There are no such integers between 47 and 55. * _g_(4) = _g_(14) = _g_(22) = _g_(27) = _g_(39) = _g_(40) = _g_(41) = _g_(58) = 4

我们定义两个函数 #cf_span[f] 和 #cf_span[g] 作用于正整数上。你需要处理 #cf_span[Q] 个查询。在每个查询中，你会得到三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k]。你需要输出在区间 #cf_span[l] 到 #cf_span[r]（包含端点）中，满足 #cf_span[g(x) = k] 的整数 #cf_span[x] 的个数。输入的第一行包含一个整数 #cf_span[Q]（#cf_span[1 ≤ Q ≤ 2 × 105]），表示查询的个数。接下来 #cf_span[Q] 行，每行包含三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k]（#cf_span[1 ≤ l ≤ r ≤ 106, 1 ≤ k ≤ 9]）。对于每个查询，输出一行，包含该查询的答案。在第一个例子中： ## Input 输入的第一行包含一个整数 #cf_span[Q]（#cf_span[1 ≤ Q ≤ 2 × 105]），表示查询的个数。#cf_span[Q] 行接下来，每行包含三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k]（#cf_span[1 ≤ l ≤ r ≤ 106, 1 ≤ k ≤ 9]）。 ## Output 对于每个查询，输出一行，包含该查询的答案。 [samples] ## Note 在第一个例子中：#cf_span[g(33) = 9]，因为 #cf_span[g(33) = g(3 × 3) = g(9) = 9]；#cf_span[g(47) = g(48) = g(60) = g(61) = 6]；在 #cf_span[47] 和 #cf_span[55] 之间不存在满足条件的整数；#cf_span[g(4) = g(14) = g(22) = g(27) = g(39) = g(40) = g(41) = g(58) = 4]。

**Definitions** Let $ f, g : \mathbb{Z}^+ \to \mathbb{Z}^+ $ be two functions defined on positive integers. **Constraints** 1. $ Q \in \mathbb{Z} $, $ 1 \leq Q \leq 2 \times 10^5 $ 2. For each query: - $ l, r, k \in \mathbb{Z} $ - $ 1 \leq l \leq r \leq 10^6 $ - $ 1 \leq k \leq 9 $ **Objective** For each query $ (l, r, k) $, compute: $$ \left| \left\{ x \in \mathbb{Z} \mid l \leq x \leq r \text{ and } g(x) = k \right\} \right| $$

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Recursive Queries",
    "description": {
      "content": "Let us define two functions _f_ and _g_ on positive integer numbers. You need to process _Q_ queries. In each query, you will be given three integers _l_, _r_ and _k_. You need to print the number of",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF932B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let us define two functions _f_ and _g_ on positive integer numbers.\n\nYou need to process _Q_ queries. In each query, you will be given three integers _l_, _r_ and _k_. You need to print the number of...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们定义两个函数 #cf_span[f] 和 #cf_span[g] 作用于正整数上。\n\n你需要处理 #cf_span[Q] 个查询。在每个查询中，你会得到三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k]。你需要输出在区间 #cf_span[l] 到 #cf_span[r]（包含端点）中，满足 #cf_span[g(x) = k] 的整数 #cf_span[x]...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ f, g : \\mathbb{Z}^+ \\to \\mathbb{Z}^+ $ be two functions defined on positive integers.  \n\n**Constraints**  \n1. $ Q \\in \\mathbb{Z} $, $ 1 \\leq Q \\leq 2 \\times 10^5 $  \n2. For eac...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments