ABC243 G - Sqrt (600)
コンテスト中の考察
1回あたり値は半分以下になるので63回目以降は1になるだけで変化のしようが無いから考える必要が無い
1回後で考えてもまだ範囲が広いので2回後で考えると$ \lfloor \sqrt[4]{x} \rfloor 以下になる
$ dp[i][j] でi回後に値jである場合の数を考えたが値が小さくなってしまったりオーバフローしたりして駄目
またlong doubleにしないとsqrtの精度が足りなさそう
解説の解法
$ \lfloor \sqrt[4]{x} \rfloor 以下については累積和を使って先に答えを求めておく
$ dp_i = ru_{\sqrt{i}}, ru_i = ru_{i-1} + dp_i
iの次は1以上$ \sqrt{i}以下の値が全て取れるため上のようになる
最後に$ \sum_{i=1}^{\lfloor \sqrt[4]{x} \rfloor } (\lfloor \sqrt{x} \rfloor - i^2 + 1) dp_i が答え
$ (\lfloor \sqrt{x} \rfloor - i^2 + 1) が$ Xの次に取ることができる値の範囲になる
$ \lfloor \sqrt[4]{x} \rfloor について全て計算するので$ \mathcal{O}(x^{\frac{1}{4}})