Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

tanishq2507's blog

By tanishq2507, history, 18 months ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
18 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
18 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

In base 10, you can decompose numbers by their decimal cases, for example 832=8102+3101+2100. The same goes for an arbitrary base B>1.

Let n be a number in base B with digits dkdk1d1d0. Following the same logic as of base 10, n can be written as dkBk+dk1Bk1++d0B0. 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(dkBk1+dk1Bk2++d1B0)+d0. By Euclid's division lemma, the quotient of the division of n by B is dkBk1+dk1Bk2++d1B0, and the remainder is d0. Observe that the quotient of that division is the base B number dkdk1d1, 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.