\(X\) が \(1\) 文字のとき、答えは \(0\) か \(1\) です。そうでない場合を考えます。

\(X\) を \(n\) 進法表記とみなしたときの値を \(f(n)\) とすると、\(f\) は狭義単調増加です。したがって、\(f(n)\leq M\) を満たすような最大の \(n\) を二分探索により求めることができ、問題が解けました。

\(X\) が 10 のとき、答えは最大で \(M\) 程度になります。計算過程でのオーバーフローなどに注意してください。

計算量は \(X\) の文字数を \(L\) として \(O(L \log M)\) です。適切な実装により(入力の受け取りを除いて) \(O(\log M)\) で解くこともできます。