ヒント → https://atcoder.jp/contests/agc066/editorial/9634

---

\(N=50\) の場合を解けばよいです．

[1] 観察

列 \(\bigl(d(2^ix)\mid 0\leq i\leq 50\bigr)\) は，多くの \(x\) に対して増加傾向があります．

\(2^ix\) の桁数が増加するにつれて，おおよそ桁数に比例するように各桁の和が増えていくようだと解釈できそうです．

---

[2] \(5^{50}\) の倍数の利用

適当な \(n\) に対して \(x=5^{50}n\) としてみましょう．このとき \(0\leq i\leq 50\) に対して \(2^ix\) は \(10^i\) の倍数であり，\(d(2^ix) = d(10^i\cdot 5^{50-i}n) = d(5^{50-i}n)\) という式変形ができます．[1] と同様に考えると，多くの \(n\) に対して\(d(2^ix)=d(5^{50-i}n)\) には \(5^{50-i}n\) の桁数に応じた減少傾向がありそうです．

---

[3] 平均化の利用

[2] でプロットした列を，ある減少列（期待値）にランダムなノイズを加えたもののように考えてみましょう．すると，このような列をたくさんとって平均をとると，ノイズの影響が非常に小さくなり減少列に近づいていくと考えられそうです（統計学における大数の（弱）法則という考え方です）．（ただし，writer は \(x=5^{50}n\) の場合の \(d(2^ix)\) の期待値や分散について正確な評価をしたわけではありません．）

このことから，次のような解法が発想できます：

適当な \(n_1, \ldots, n_k\) に対して \(x_j=5^{50}n_j\) を並べてできる整数を \(x\) とする．

この場合 \(0\leq i\leq 50\) に対して \(d(2^ix) = \sum_j d(2^ix_j)\) なので，\(k\) を十分大きくとれば，\(d(2^ix_j)\) の平均化として減少列が得られそうです．

---

[4] 解法

以上により，例えば次のような解法が考えられます．

• 適当に \(n_1, \ldots, n_k\) をとり，\(5^{50}n_i\) を並べたものを \(x\) とする．例えば \(k\) を \(100\) から \(200\) 程度にとり成功するまで乱択を繰り返せばすぐに解が得られる．なお，\(n_i\) を奇数にとることで，\(d(2^{49}x) > d(2^{50}x)\) が成り立ちやすくなり，より高確率で解を出力するようになる．乱択ではなく単に \(n_i = i\) などとしてもよい．
• \(5^{50}, 5^{51}, \ldots\) を並べた数を解としてもよい．例えば \(5^{50}, \ldots, 5^{65}\) を並べると \(651\) 桁の解が得られる．この解は減少傾向の平均化という以外に，移動平均によりノイズを消すという発想からも得られるだろう．