CodeIQ 挑戦の記録 : 「ロング・ロング・ストリング」問題

CodeIQというサイトで問題に挑戦した記録です。

問題文を要約すると下記の通り

自然数 ${n}$ に対して関数 ${F(n)}$ を ${{n}^{n}}$ を10進数で表した時の桁数と定義する。
2以上の自然数 ${m}$ に対して関数 ${F(n)=m}$ となる ${n}$ の値を ${G(m)}$ と定義する。
そのような ${n}$ が存在しない時は ${G(m)=-1}$ と定義する。
標準入力から ${ m \ (2 \leq m \leq {10}^{10})}$ が与えられる。
${G(m)}$ を出力する。

方針

題意より ${F(n)=m}$ は次の数式で表す事ができる。
\begin{align} floor( \log_{10} {n}^{n} ) + 1 =m \end{align}

これを変形し、
\begin{align} m-1 \leq \log_{10} {n}^{n} < m
\end{align} これを ${n}$ について解けば ${O(1)}$ のコードが書けるが、この数式を解く能力は自分には無いのであっさり諦める。
上式を
\begin{align} floor( n \log_{10} n)+1=m \end{align}
と変形し ${F(n)=m}$ となる ${n}$ を探索する事にする。
但し、線形探索 ${O(N)}$ では、入力の最大 ${{10}^{10}}$ に対して1秒の時間制限をクリアする事は出来無い。
そこで、二分探索 ${O(\log N)}$ を自前で実装する事とする。