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:

Screen Shot 2016-06-24 at 10.24.04 PM

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 ≤ 109
1 ≤ m ≤ 109

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 = m1;

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));

}

}

}

}

 

 

Advertisements