ABC139 D - ModSum

問題はこちら atcoder.jp

方針

直感で解きました。

以下の証明ミスってます。修正中です。

後付けで証明もしておきます。 求める和は， と表せます。ここで，ある整数を で割った余りは （最大でも ）なので， です。 { } { } と並べ替えたとき，これを満たします。

コード

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    long long n;
    cin>>n;
 
    cout<<n*(n-1)/2<<endl;
}