ABC192/D - Base n

問題

• 引用元://atcoder.jp/contests/abc192/tasks/abc192_d

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

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

解法

$X$ を $n$ 進数と見なすとはつまり, 列 $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$ 種類が答えである.