[AtCoder] ABC 139 D – ModSum

問題

方針

制約から考える

\( N = 10^9 \) と制約がきついので、計算量は \( O(\sqrt{N})\) や \( O(1) \) などが考えられます。また、こういった問題は、\( N = 1 \) から実際にシミュレーションを行い規則性を見つけることができることが多いので、実際にそうしてみます。

シミュレーション

\( N = 1,  N = 2 \) のとき

\( N = 1 \) のときは \( 0 \) で、\( N = 2 \) のときは \( 1 \) です。

\( N \geq 3 \)

\( N = 3 \) のとき、\( 3 \) となり、\( N = 4 \) のとき、\( 6 \) となり、\( N = 5 \) のとき \( 10 \) となるので、

\[\dfrac{N(N-1)}{2}\]

となることが考えられます。

コード