1301-C, *1700

Problem - C - Codeforces

 

풀이

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
map<int, ll> dp;
 
ll H(ll n)
{
    if(dp[n] == 0) {
        ll ret = (n+1)*n/2;
        dp[n] = ret;
    }
    return dp[n];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        if((n+1)/2 >= n-m) cout << H(n) - (n-m) << endl;
        else{
            ll res = H(n);
            int s = m+1;
            int small = (n-m)/s;
            int big = small + 1;
            int big_cnt = n-m-small*s;
            int small_cnt = s - big_cnt;
            res -= big_cnt*H(big);
            res -= small_cnt*H(small);
            cout << res << endl;
        }
 
    }
 
    return 0;
}cs