codeforces-scrape

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

1985G.md (1088B)


      1 Source: https://codeforces.com/problemset/problem/1985/G
      2 
      3 G. D-Function
      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 $D(n)$ represent the sum of digits of $n$. For how many integers $n$ where $10^{l} \leq n \lt 10^{r}$ satisfy $D(k \cdot n) = k \cdot D(n)$? Output the answer modulo $10^9+7$.
     22 
     23 Input
     24 
     25 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) – the number of test cases.
     26 
     27 Each test case contains three integers $l$, $r$, and $k$ ($0 \leq l \lt r \leq 10^9$, $1 \leq k \leq 10^9$).
     28 
     29 Output
     30 
     31 For each test case, output an integer, the answer, modulo $10^9 + 7$.
     32 
     33 Example
     34 
     35 Input
     36 
     37 ```
     38 6
     39 
     40 0 1 4
     41 
     42 0 2 7
     43 
     44 1 2 1
     45 
     46 1 2 3
     47 
     48 582 74663 3
     49 
     50 0 3 1
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 2
     57 3
     58 90
     59 12
     60 974995667
     61 999
     62 ```
     63 
     64 Note
     65 
     66 For the first test case, the only values of $n$ that satisfy the condition are $1$ and $2$.
     67 
     68 For the second test case, the only values of $n$ that satisfy the condition are $1$, $10$, and $11$.
     69 
     70 For the third test case, all values of $n$ between $10$ inclusive and $100$ exclusive satisfy the condition.