Ayoub's function
Contest: Codeforces Round 619 (Div. 2)
Difficulty rating: 1700
Tags: binary search, combinatorics, greedy, math, strings

Ayoub thinks that he is a very smart person, so he created a function $$$f(s)$$$, where $$$s$$$ is a binary string (a string which contains only symbols "0" and "1"). The function $$$f(s)$$$ is equal to the number of substrings in the string $$$s$$$ that contains at least one symbol, that is equal to "1".

More formally, $$$f(s)$$$ is equal to the number of pairs of integers $$$(l, r)$$$, such that $$$1 \leq l \leq r \leq |s|$$$ (where $$$|s|$$$ is equal to the length of string $$$s$$$), such that at least one of the symbols $$$s_l, s_{l+1}, \ldots, s_r$$$ is equal to "1".

For example, if $$$s = $$$"01010" then $$$f(s) = 12$$$, because there are $$$12$$$ such pairs $$$(l, r)$$$: $$$(1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 4), (4, 5)$$$.

Ayoub also thinks that he is smarter than Mahmoud so he gave him two integers $$$n$$$ and $$$m$$$ and asked him this problem. For all binary strings $$$s$$$ of length $$$n$$$ which contains exactly $$$m$$$ symbols equal to "1", find the maximum value of $$$f(s)$$$.

Mahmoud couldn't solve the problem so he asked you for help. Can you help him?

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$)  — the number of test cases. The description of the test cases follows.

The only line for each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 10^{9}$$$, $$$0 \leq m \leq n$$$) — the length of the string and the number of symbols equal to "1" in it.

Output format:
For every test case print one integer number — the maximum value of $$$f(s)$$$ over all strings $$$s$$$ of length $$$n$$$, which has exactly $$$m$$$ symbols, equal to "1".

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, there exists only $$$3$$$ strings of length $$$3$$$, which has exactly $$$1$$$ symbol, equal to "1". These strings are: $$$s_1 = $$$"100", $$$s_2 = $$$"010", $$$s_3 = $$$"001". The values of $$$f$$$ for them are: $$$f(s_1) = 3, f(s_2) = 4, f(s_3) = 3$$$, so the maximum value is $$$4$$$ and the answer is $$$4$$$.

In the second test case, the string $$$s$$$ with the maximum value is "101".

In the third test case, the string $$$s$$$ with the maximum value is "111".

In the fourth test case, the only string $$$s$$$ of length $$$4$$$, which has exactly $$$0$$$ symbols, equal to "1" is "0000" and the value of $$$f$$$ for that string is $$$0$$$, so the answer is $$$0$$$.

In the fifth test case, the string $$$s$$$ with the maximum value is "01010" and it is described as an example in the problem statement.

Example input:
5
3 1
3 2
3 3
4 0
5 2

Example output:
4
5
6
0
12

Editorial:
We can calculate the number of sub-strings that has at least one symbol equals to "1" like this:
$$$f(s)$$$ $$$=$$$ (number of all sub-strings) $$$-$$$ (number of sub-strings that doesn't have any symbol equals to "1").
if the size of $$$s$$$ is equal to $$$n$$$, $$$f(s)$$$ $$$=$$$ $$$\frac{n\cdot(n+1)}{2}$$$ $$$-$$$ (number of sub-strings that doesn't have any symbol equals to "1").
if we want to calculate them, we only need to find every continuous sub-string of 0's if it's length was $$$l$$$, then we subtract $$$\frac{l\cdot(l+1)}{2}$$$.
now we have a string contains $$$(n - m)$$$ "0" symobol, and we want to divide these symbols into $$$(m+1)$$$ groups so that the summation of $$$\frac{l\cdot(l+1)}{2}$$$ for every group is minimised.
The best way is to divide them into equal groups or as equal as possible.
let $$$z$$$ be the number of zeroes in the string, $$$z=(n - m)$$$, and g be the number of groups, $$$g=m+1$$$.
let $$$k$$$ equal to $$$\lfloor$$$ $$$\frac{z}{g}$$$ $$$\rfloor$$$.
we should give every group $$$k$$$ zeroes, except for the first $$$(z\mod g)$$$ groups, we should give them $$$k+1$$$ zeroes.
So the answer is $$$\frac{n.(n+1)}{2}$$$ $$$-$$$ $$$\frac{k.(k+1)}{2} \cdot g$$$ $$$-$$$ $$$(k + 1) \cdot (z\mod g)$$$.
Complexity is $$$O(1)$$$.
code:https://ideone.com/rk5nDE