This base conversion algorithm has an application in this problem 1811E - Living Sequence.Why does the base conversion work here.What do the remainders signify in the base conversion?
№ | Пользователь | Рейтинг |
---|---|---|
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 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
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 |
This base conversion algorithm has an application in this problem 1811E - Living Sequence.Why does the base conversion work here.What do the remainders signify in the base conversion?
Название |
---|
you can think of it like just converting to base 9 (because there are 9 digits) but with different namings/symbols.
In base 10, you can decompose numbers by their decimal cases, for example $$$832 = 8\cdot 10^2 + 3\cdot 10^1 + 2\cdot 10^0$$$. The same goes for an arbitrary base $$$B > 1$$$.
Let $$$n$$$ be a number in base $$$B$$$ with digits $$$d_k d_{k-1} \ldots d_1 d_0$$$. Following the same logic as of base $$$10$$$, $$$n$$$ can be written as $$$d_k\cdot B^k + d_{k-1} \cdot B^{k-1} + \ldots + d_0 \cdot B^0$$$. Now, notice that, all digits have "values" divisible by $$$B$$$, except for digit $$$0$$$. So, we can write $$$n$$$ in the follow way $$$n = B(d_k\cdot B^{k-1} + d_{k-1} \cdot B^{k-2} + \ldots + d_1 \cdot B^0) + d_0$$$. By Euclid's division lemma, the quotient of the division of $$$n$$$ by $$$B$$$ is $$$d_k\cdot B^{k-1} + d_{k-1} \cdot B^{k-2} + \ldots + d_1 \cdot B^0$$$, and the remainder is $$$d_0$$$. Observe that the quotient of that division is the base $$$B$$$ number $$$d_k d_{k-1} \ldots d_1$$$, which is our original number $$$n$$$, without it's last digit. Therefore, we can repeat this procedure until we find all the digits of $$$n$$$.
In the problem you mentioned, you're basically counting in base $$$9$$$, except we are using the digits $$$0, 1, 2, 3, 5, 6, 7, 8, 9$$$ instead of $$$0$$$ to $$$8$$$. So, all you need to do is find the base $$$9$$$ number, and map the digits $$$0, 1, \ldots 8$$$ to $$$0, 1, 2, 3, 5, 6, 7, 8, 9$$$.
Thank you for the base conversion explanation.
op explanation