codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

932B.md (1505B)


      1 Source: https://codeforces.com/problemset/problem/932/B
      2 
      3 B. Recursive Queries
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Let us define two functions *f* and *g* on positive integer numbers.
     22 
     23  ![](https://espresso.codeforces.com/affd4e3cdcadc3ba7dbceb6a2c0eb4ba928c1e4b.png)
     24 
     25 ![](https://espresso.codeforces.com/120df92771639f1f51a4b216dccd3ed7c32bb859.png)
     26 
     27 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*.
     28 
     29 Input
     30 
     31 The first line of the input contains an integer *Q* (1 ≤ *Q* ≤ 2 × 105) representing the number of queries.
     32 
     33 *Q* lines follow, each of which contains 3 integers *l*, *r* and *k* (1 ≤ *l* ≤ *r* ≤ 106, 1 ≤ *k* ≤ 9).
     34 
     35 Output
     36 
     37 For each query, print a single line containing the answer for that query.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 4  
     45 22 73 9  
     46 45 64 6  
     47 47 55 7  
     48 2 62 4
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 1  
     55 4  
     56 0  
     57 8
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 4  
     64 82 94 6  
     65 56 67 4  
     66 28 59 9  
     67 39 74 4
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 3  
     74 1  
     75 1  
     76 5
     77 ```
     78 
     79 Note
     80 
     81 In the first example:
     82 
     83 * *g*(33) = 9 as *g*(33) = *g*(3 × 3) = *g*(9) = 9
     84 * *g*(47) = *g*(48) = *g*(60) = *g*(61) = 6
     85 * There are no such integers between 47 and 55.
     86 * *g*(4) = *g*(14) = *g*(22) = *g*(27) = *g*(39) = *g*(40) = *g*(41) = *g*(58) = 4