本解説において、次の記号を用います。

• 正の整数 \(X\) に対して、黒板に \(X\) がひとつ書かれた状態から始めたときの操作後の総積の最大値を、\(f(X)\) と書く。
• \(X_- = \lfloor X/2\rfloor\), \(X_+ = \lceil X/2\rceil\) と書く。

[1] \(f(X)\) の漸化式

次が成り立ちます：

• \(f(1) = 1\)
• \(f(X) = \max\{X, f(X_-)f(X_+)\}\) （\(X\geq 2\) のとき）

実際、求める値は次の \(2\) つの場合の最大値です。

• 操作を一度も行わない場合：操作後の総積は \(X\) である。
• 操作を一度以上行う場合：まず操作を一度行うと、黒板の状態は \((X_-,X_+)\) へと変化する。その後は、\(X_-, X_+\) それぞれを総積が最大になるように操作するのが最適である。この場合、操作後の総積の最大値は \(f(X_-)f(X_+)\) である。

さらに、\(f(X) = \max\{X, f(X_-)f(X_+)\}\) において \(\max\) のどちら側が大きいかを考えると、次が成り立つことが分かります：

• \(f(X) = X\) （\(X\leq 4\) のとき）
• \(f(X) = f(X_-)f(X_+)\) （\(5\leq X\) のとき）

実際、\(X\leq 4\) のときは漸化式 \(f(X) = \max\{X, f(X_-)f(X_+)\}\) に従って計算すれば分かります。\(5\leq X\) のときは、

\[f(X_-)f(X_+) \geq X_-X_+ \geq \frac{X-1}{2}\cdot \frac{X}{2} = \frac{X-1}{4}\cdot X\geq X\]

より \(f(X_-)f(X_+)\geq X\) が成り立ちます。

[2] 計算アルゴリズム・計算量解析

[1] の漸化式によって、再帰的に \(f(X)\) を計算していきます。この際、一度計算した \(f(X)\) の値をメモして使いまわすメモ化再帰という方法をとることで、\(f(X)\) を効率よく計算できます。

• 解答例 (Python)：https://atcoder.jp/contests/arc135/submissions/29019824
• 解答例 (C++)：https://atcoder.jp/contests/arc135/submissions/29019934

\(f(X)\) の計算の過程で、より小さな \(x\) に対する \(f(x)\) の値をいくつか計算する必要があります。この計算に現れる \(x\) は、ある \(k\) に対して \(\lfloor X/2^k\rfloor\) または \(\lceil X/2^k\rceil\) と書けるものに限られます（\(k\) 回目の再帰での \(x\) がこの形であることを、\(k = 0, 1, 2, \ldots\) の順に証明できます）。

したがって、\(2^{K-1}\leq X < 2^{K}\) となる \(K\) をとれば、計算対象となる \(f(x)\) は高々 \(2K\) 個しか存在せず、本問題は \(\Theta(\log X)\) 時間（メモ化の方法によっては \(\Theta(\log X \log\log X)\) 時間）で解くことができます。