# Hackerrank Solution: Easy sum

Little Kevin had never heard the word 'Infinitum'. So he asked his mentor to explain the word to him. His mentor knew that 'Infinitum' is a very large number. To show him how big Infinitum can be, his mentor gave him a challenge: to sum the numbers from *1* up to *N*. The sum started to get really large and was out of `long long int`

range. And so the lesson was clear.

Now his mentor introduced him to the concept of *mod* and asked him to retain only the remainder instead of the big number. And then, he gave him a formula to compute:

\[\sum\limits_{i=1}^n (i \% m) \]

**Input Format**

The first line contains *T*, the number of test cases. *T* lines follow, each containing 2 space separated integers *N m*

**Output Format**

Print the result on new line corresponding to each test case.

**Constraint**

1 ≤ *T* ≤ 1000

1 ≤ *N* ≤ 10^{9}

1 ≤ *m* ≤ 10^{9}

**Sample Input**

```
3
10 5
10 3
5 5
```

**Sample Output**

```
20
10
10
```

**Explanation**

Case 1: *N* = 10 *m* = 5,

1%5 + 2%5 + 3%5 + 4%5 + 5%5 + 6%5 + 7%5 + 8%5 + 9%5 + 10%5 = 20.

Similar explanation follows for Case 2 and 3.

## Solution

It's clear that for the first \(m\) numbers the sum can be calculated with the triangular equation \(\frac{1}{2}m(m - 1)\). Since we operate under the modulo, the sequence starts from anew and get exactly \(\left\lfloor\frac{n}{m}\right\rfloor\) of such blocks and for the rest \(n \% m\) we can again use the triangular numbers formula \(\frac{1}{2}(n \% m)(n \% m + 1)\). We can now combine all these information:

\[\sum\limits_{i=1}^n (i \% m) =\frac{1}{2}\left( \left\lfloor\frac{n}{m}\right\rfloor m(m - 1) + (n \% m) \cdot (n \% m + 1)\right)\]

When we now substitute \(n - m \left\lfloor\frac{n}{m}\right\rfloor = n \% m\), we get

\[\sum\limits_{i=1}^n (i \% m) =\frac{1}{2}\left( m n + (n \% m) (n \% m - m + 2) - n \right)\]

This is enough to pass all tests, but the equation does not hold for \(m> n\), where it falls back to the normal summation equation. Anyway, the implementation in ruby then looks as:

gets.to_i.times{ n, m = gets.split.map(&:to_i) if m <= n puts (m * n + (n % m) * (n % m - m + 2) - n) / 2 else puts n * (n + 1) / 2 end }