ABC190 D Staircase Sequences
等差数列の長さを全探索し固定して考える. 長さが分かれば最初の値は一意に定まることがわかる. ここで各値の構造に注目してみると, 最初の値を$ a, 長さを$ kとして総和は$ \sum_{i=0}^{k - 1} a+i = ak + \sum_{i=0}^{k - 1} i = ak + \frac{k(k-1)}{2}と表せることがわかる.
よって$ ak + \frac{k(k-1)}{2} = Nなる$ aが存在するかどうか調べればよく, これは$ N - \frac{k(k-1)}{2}が$ kで割り切れるかどうかが必要十分条件となる. 計算量は$ O(\sqrt N)である.