ABC190 D - Staircase Sequences (400)
最初の考察
１以上の数だけからなる等差数列だけ考える
これに対応する0以下を使った等差数列が1個作れるので最終的に2倍する
$ N が偶数なら奇数個の要素、奇数なら偶数個の要素でしか表せないはず
これを数え上げる
嘘だった
次の考察
等差数列の最大長を考える
長さを$ k としたときに$ N - \frac{k(k-1)}{2} が$ k で割り切れればその長さの配列が作れる
最初と同様に初項が1以上の場合だけ考える
$ k^2-k-2N \lt 0であれば良いので$ kは$ 3 \sqrt Nくらいまで考えれば良い
後は長さ1から順にその長さで割りきれるようにかつ初項が1以上になるかを判定して、作れる長さの数の和が答え
長さごとの判定は$ O(1)なので全体で$ O(\sqrt N)