😺

ABC192/D - Base n

1 min read

問題

[0-9]+ な文字列 X と整数 M がある.
Xn 進数と見なして M 以下であるような数は何種類作れるか.

ただし nX に出現する各文字 (0-9) より大きいとする.
(例えば 4 という文字は n>4 進数でしか解釈できない.)

解法

Xn 進数と見なすとはつまり, 列 X をその頭から

X = (X_1, X_2, \ldots, X_k)

だとすると
x = ( \cdots ((X_1 \times n) + X_2) \times n) + \cdots) + X_k

という数を作ることに他ならない.
この数は n によってきまるから改めて f(n) とでも書くのが自然だろう.

直感的にも
f(1) \leq f(2) \leq \cdots f(n) \leq \cdots
なのは明らかだから, M 以下であるようなのはギリギリ

F(N) \leq M

になるような N を見つければそれ以下はすべてOKだとわかる.
というわけで二分探索をすれば良い

気をつける点

X が長さ1の文字列の場合,

f(n) = X_1

となって n によらない.
そこで X_1 \leq M なら何進数であっても M 以下になってしまう.
ここで問題は「数の種類」だったので, その場合は 1 種類が答えである.

Discussion

ログインするとコメントできます