\(N\) の \(b\) 進数表現の桁数 \(d\) として考えられるのは \(d = 2, 3, \ldots, \lfloor \log_2 N \rfloor + 1\) です。 よって、これらの \(d\) それぞれについて 「 \(N\) の \(b\) 進数表現が \(d\) 桁でありその各桁が \(0\) または \(1\) であるような整数 \(b\) の個数」を十分高速に求められれば良いです。

以下、\(d\) を固定し「 \(N\) の \(b\) 進数表現が \(d\) 桁でありその各桁が \(0\) または \(1\) であるような整数 \(b\) 」（以下、良い整数と呼ぶ）の個数を求めます。

\(d = 2\) のとき、\(b = N\) と（ \(N \geq 3\) ならば） \(b = N-1\) が良い整数です。

\(d \geq 3\) の場合を考えます。 \(b\) が良い整数であるには、\(N\) が \(d\) 桁の \(b\) 進数表記で \(1000\ldots 0\) 以上 \(111\ldots 1\) 以下である、 すなわち、\(N\) が区間 \([l_b, r_b] \coloneqq [b^{d-1}, b^{d-1} + b^{d-2} + \cdots + b + 1]\) に含まれることが必要です。 ここで、\(b \neq b'\) ならば、\(2\) つの区間 \([l_b, r_b], [l_{b'}, r_{b'}]\) は交わりません。実際、

\[r_{b} = \sum_{i=0}^{d-1} b^i \lt \sum_{i=0}^{d-1}\binom{d-1}{i}b^i = (b+1)^{d-1} = l_{b+1}\]

が成り立ちます（不等号は \(d \geq 3\) より）。 よって、良い整数 \(b\) になり得るのは、 \(\hat{b}^{d-1} \leq N\) を満たす最大の整数 \(\hat{b}\) に限られます。 したがって、この \(\hat{b}\) について実際に \(N\) を \(\hat{b}\) 進数表示し、その各桁が \(0\) または \(1\) であるかを確認すれば良いです。 \(\hat{b}^{d-1} \leq N\) を満たす最大の整数 \(\hat{b}\) は二分探索によって十分高速に求められます。