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?
# | User | Rating |
---|---|---|
1 | jiangly | 3845 |
2 | tourist | 3798 |
3 | orzdevinwang | 3706 |
4 | jqdai0815 | 3682 |
5 | ksun48 | 3589 |
6 | Ormlis | 3532 |
7 | Benq | 3468 |
8 | Radewoosh | 3463 |
9 | ecnerwala | 3451 |
10 | Um_nik | 3450 |
# | User | Contrib. |
---|---|---|
1 | cry | 165 |
2 | Qingyu | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 157 |
5 | Dominater069 | 156 |
6 | adamant | 154 |
7 | djm03178 | 151 |
8 | luogu_official | 149 |
9 | awoo | 147 |
10 | TheScrasse | 145 |
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?
Name |
---|
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⋅102+3⋅101+2⋅100. The same goes for an arbitrary base B>1.
Let n be a number in base B with digits dkdk−1…d1d0. Following the same logic as of base 10, n can be written as dk⋅Bk+dk−1⋅Bk−1+…+d0⋅B0. 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(dk⋅Bk−1+dk−1⋅Bk−2+…+d1⋅B0)+d0. By Euclid's division lemma, the quotient of the division of n by B is dk⋅Bk−1+dk−1⋅Bk−2+…+d1⋅B0, and the remainder is d0. Observe that the quotient of that division is the base B number dkdk−1…d1, 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,…8 to 0,1,2,3,5,6,7,8,9.
Thank you for the base conversion explanation.
op explanation