CodeIQというサイトで問題に挑戦した記録です。
問題文を要約すると下記の通り
- 自然数
に対して関数
を
を10進数で表した時の桁数と定義する。
- 2以上の自然数
に対して関数
となる
の値を
と定義する。
そのようなが存在しない時は
と定義する。
- 標準入力から
が与えられる。
を出力する。
方針
題意より は次の数式で表す事ができる。
\begin{align}
floor( \log_{10} {n}^{n} ) + 1 =m
\end{align}
これを変形し、
\begin{align}
m-1 \leq \log_{10} {n}^{n} < m
\end{align}
これをについて解けば
のコードが書けるが、この数式を解く能力は自分には無いのであっさり諦める。
上式を
\begin{align}
floor( n \log_{10} n)+1=m
\end{align}
と変形しとなる
を探索する事にする。
但し、線形探索では、入力の最大
に対して1秒の時間制限をクリアする事は出来無い。
そこで、二分探索を自前で実装する事とする。
実装
提出したコードは下記の通り
(実際は下記をワンライナーにしたもの。134byte)
では、
Sponsored Link