## Problem: Easy sum

*Difficulty: Easy

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:

**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.

How to solve:

Base on the formula to calculate sum of first nth numbers (1+2+…+nth), and the property of mod. I came up with the formula below

init:

n <- N;

m <-m;

k = (floor)n/m;

m -= 1;

remainder = n%m;

if remainder == 0

result will be ((m*(m+1))/2)*k

otherwise

result will be ((m*(m+1))/2)*k + ((remainder*(remainder+1)/2))

As I said above, n*(n+1) / 2 is the formula to calculate the first n numbers (1,2,3,…n)

I will take two special cases that are the only two cases in this problem you need to pay attention.

Case 1: remainder == 0

n = 10, m = 5 (n mod 10 == 0)

Sum of first 10 number is :

1+2+4+5+6+7+8+9+10

Sum of first 10 number mod 5 is

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

As you may notice, 5%5 and 10%5 bot produce 0

and

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

It mean we can split the original expression into 2 equal part (n/m = 10/5 = 2)

And we just need to calculate sum of first (m-1) number, in this case is 5-1=4,

multiply that with k = n/m = 10/2 = 2.

Case 2: remainder != 0

We will use the value of case 1 and add it with the value produced by the formula we will discover here.

n = 10, m = 3

k = n/m = 10/3 (floor) = 3

remainder = 10 mod 3 = 1;

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

3%3 = 6%3 = 9%3 = 0

1%3 + 2%3 = 4%3 + 5%3 = 7%3 + 8%3 (3 parts = 10/3(floor) = 3)

10%3 = 1 (1 here is not the remainder of 10 mod 3, 1 is the sum of first 1 numbers)

We just need to calculate the sum of first (m-1), here is 3-1, numbers. And multiply that with 3 (as with Case 1) . About the remainder, 10%3 = 1%3 = sum of first 1 numbers

Another example:

n = 10, m = 4

k = n / m = 2;

remainder = 2;

1%4+2%4+3%4 = 5%4+6%4+7%4 (2 parts = k parts)

9%4+10%4 = 1%4+2%4=1+2 (sum of first 2 numbers)

You got the idea, right :>

Took 200 to 300 ms (depend on input)

Implementation: Java

Here I’m using BigInteger because the output will exceed the long’s bound in Java. (10^17)

import java.math.BigInteger;

import java.util.Scanner;

public class EasySum {

publicstaticvoidmain(String[] args) {

Scannerinput = new Scanner(System.in);

int t = input.nextInt();

int n,m,k,remainder;

for(int i = 1; i <= t; ++i) {

n = input.nextInt();

m = input.nextInt();

k = (int) Math.floorDiv(n,m);

remainder= n%m;

m = m–1;

BigIntegerbigK = BigInteger.valueOf(k);

BigIntegerbigM = BigInteger.valueOf(m);

BigIntegerbigRemainder = BigInteger.valueOf(remainder);

if(remainder == 0) {

//(long) ((m*(m+1))/2)*k;

System.out.println(bigM.multiply(bigM.add(BigInteger.ONE)).divide(BigInteger.valueOf(2)).multiply(bigK));

} else {

//(long) ((m*(m+1))/2)*k + ((remainder*(remainder+1)/2));

BigIntegerb1 = bigM.multiply(bigM.add(BigInteger.ONE)).divide(BigInteger.valueOf(2)).multiply(bigK);

BigIntegerb2 = bigRemainder.multiply(bigRemainder.add(BigInteger.ONE)).divide(BigInteger.valueOf(2));

System.out.println(b1.add(b2));

}

}

}

}

## Reply