| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
For numbers with l+1 digits, there are floor(9/k) + 1 (say a) options per digit, hence the total number of numbers should be a^(l+1). Similarly, for l+2 digits, a^(l+2). So on for r digits, a^(r).
Shouldn't the answer be the sum of these numbers?
a^(l+1) + a^(l+2) + .... + a^r
Auto comment: topic has been updated by ayushanshul07 (previous revision, new revision, compare).
say l =3 , r =5; means your n will be between 1000 and 100000 1000,1001,1002...1999,... ,99999 will be your probable numbers out of which the valid numbers must have each digits lesser than or equal to 9/k. now say we didnt have a lower limit r then the valid answer would have been : a^r , but we have a lower bound l so we over counted those numbers so we can just do -a^l, final answer being a^r -a^l.
why your approach is wrong : a^r is the number of valid numbers till number of digits are r thats simple catch you missed. so you basically are over counting. why does a^r include all valid numbers upto r digits : since you are also counting 0 as valid digit hence we can get all r-1 , r-2, ... 1 digit numbers too!!
Understood, thanks!