Блог пользователя tanishq2507

Why does the base 10 to base b conversion algorithm work?
Автор tanishq2507, история, 15 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

you can think of it like just converting to base 9 (because there are 9 digits) but with different namings/symbols.

→ Ответить
»
15 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

In base 10, you can decompose numbers by their decimal cases, for example

Unable to parse markup [type=CF_MATHJAX]

. The same goes for an arbitrary base

Unable to parse markup [type=CF_MATHJAX]

.

Let $$$n$$$ be a number in base $$$B$$$ with digits

Unable to parse markup [type=CF_MATHJAX]

. Following the same logic as of base $$$10$$$, $$$n$$$ can be written as

Unable to parse markup [type=CF_MATHJAX]

. Now, notice that, all digits have "values" divisible by $$$B$$$, except for digit $$$0$$$. So, we can write $$$n$$$ in the follow way

Unable to parse markup [type=CF_MATHJAX]

. By Euclid's division lemma, the quotient of the division of $$$n$$$ by $$$B$$$ is

Unable to parse markup [type=CF_MATHJAX]

, and the remainder is $$$d_0$$$. Observe that the quotient of that division is the base $$$B$$$ number

Unable to parse markup [type=CF_MATHJAX]

, 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

Unable to parse markup [type=CF_MATHJAX]

instead of $$$0$$$ to $$$8$$$. So, all you need to do is find the base $$$9$$$ number, and map the digits

Unable to parse markup [type=CF_MATHJAX]

to

Unable to parse markup [type=CF_MATHJAX]

.
→ Ответить