tookunn’s diary

主に競技プログラミング関係

AtCoder Beginner Contest 190 D - Staircase Sequences

ABC

問題

考察

まず、公差1の等差数列の総和の特性を見つけるために
公差1の等差数列の総和を求める式を考える。

総和をN、初項をA、項数をLとすると
$N = \frac{1}2 \times L \times (A + A + L - 1)$
$N = \frac{1}2 L (2A + L - 1)$
扱いやすいように両辺に2を掛けて
$2N = L (2A + L - 1)$ となる。

この式から
$2N$ は、 $L$ または $(2A + L - 1)$ で割り切れる値だということが分かる。（つまり約数である）

分かりやすくすると
$2N = X \times Y$ という式で表すことができて、 $2N$ は $X$ と $Y$ を約数に持ち、
$X = L, Y = (2A + L - 1)$ または $X = (2A + L - 1), Y = L$ であるということ。

ここで $L$ さえ分かれば $2N$ から $(2A + L - 1)$ も求めることができて良さそうなので
$L$ を $\sqrt{2N}$ まで全部試していく。
$2N$ は偶数なので、 $X$ と $Y$ のどちらかは偶数であり、 $2A$ が偶数であることを
確かめていき、OKならカウントしていく。

ソースコード