ABC171 C. One Quadrillion and One Dalmatians
問題
a～zまでの文字を使って整数Nを表現する。
N=1のときa、N=26のときz、N=27のときaa、N=702のときzzのように、Nを1増やすたびに一番最後の文字が
- zでない場合はインクリメント
- zの場合は、一つ前の文字をインクリメントしてaに戻す
ようなことを繰り返して作る。
このとき、Nがどのような文字になるかを答えよ。
制約
- 1 <= N <= 10^15 + 1
解法
x進数のように見えるが、微妙に異なる。
例として、a=0,z=25として26進数を考えると、zの次が1*26 + 0でbaのようになってしまいうまく表現できない。
また、0を別に考えたa=1,z=26として27進数を考えると、zの次が1*27 + 0でa0のようになってしまうため、0の付近でうまく表現できない。
気づくべきこととして、答えの文字長がMというのがわかった場合、そこの中では26進数になっている。
この場合、番号が何番から始まっているか？がわかれば、それを引いた整数が26進数で表現するとどうなるか？から復元すれば良い。
番号が何番から始まっているか？は、
M=1の場合、1
M=2の場合、1 + 26
M=3の場合、1 + 26 + 26^2
...
のように規則的に増えていくので、実際に増やしてみて該当する数字を求めておく。
