\(D\) からは1を引いて, 以下は 0-index で考える.

\(i\) 桁の数をすべて並べると何文字になるかを考えると, これは \(i \times (B-1) \times B^{i-1}\) 文字になる. よって, \(i\) 桁以下の数をすべて並べたときの文字数を \(S_i\) と置くと,

\[S_i = \sum_{j=1}^i j \times (B-1) \times B^{j-1} = (B-1)(1+2B+3B^2+\dots+iB^{i-1})\]

となる. ここで, \(S_i-BS_i\) を考えると,

\[(1-B)S_i = (B-1)(1+B+B^2+\dots+B^{i-1}-iB^i)\]

となるので, これを整理して,

\[S_i = iB^i - (1+B+B^2+\dots+B^{i-1}) = iB^i - \frac{B^i-1}{B-1}\]

となる. \(D\) 文字目に含まれる数値の桁数は

\[D \gt iB^i - \frac{B^i-1}{B-1}\]

であれば \(i\) より大きいので, これを満たす最大の \(i\) を二分探索で求める.

これで求めた \(D\) 桁目を含む数値の桁数を \(d\) とし, \(D\) からは \(S_{d-1}\) を引いておく.

\(D\) 桁目を含む数値が \(d\) 桁の数値のうちの何番目で, さらにその数値のうちの何桁目かは, \(D\) を \(d\) で割って, 商と余りを求めればいい. 商の方は最上位桁に1を足したものがそのまま \(D\) 桁目を含む数値になるし, その数値の何桁目かは余りを見ればいい.

多倍長計算は \(B\) 進数であることを利用すればきれいにできるのかも知れないが, 割り算が面倒だったので GMP に逃げた.