Hackerrank Solution: Easy sum

Original Problem

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⁹
1 ≤ m ≤ 10⁹

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
}