Educational Codeforces Round 37 - F. SUM and REPLACE
解法
約数の個数はかなり速いスピードで減っていって最終的に 1 or 2になる(1は最初から1の場合)
ということで各において、何百回約数の個数に変更しても2のままで無駄なことをしてるだけなのである。
よってstd::set
などを使って、2より大きいのindexを管理してそれだけを見るようにしよう。
あとはBITを更新していくだけである
提出コード
まとめ
解法そのものは早かったのだけど、std::set
をやらずにうまく右にいくの更新しようとしたらなかなか大変だった
std::set
ほんとつよいね