[AtCoder] ABC 139 D – ModSum

2019年9月2日

問題

方針

制約から考える

\( 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}\]

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

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  ll N;
  cin >> N;
  cout << N * (N - 1) / 2 << "\n";
  return 0;
}