Sum of Remainders

Problem Statement

Sum of Remainders Problem Description You are given two integers n and div . Divide every number from 1 to n (both inclusive) by div , and find the sum of all the remainders obtained. In other words, compute (1 % div) + (2 % div) + ... + (n % div) , where x % div is the remainder left when x is divided by div . Input Format Read from standard input. n div The first line contains the integer n . The second line contains the integer div . Output Format Print a single integer: the sum of the remainders of the numbers 1, 2, ..., n when each is divided by div . Constraints 0 < n < 10^5 , that is, 1 <= n <= 99999 . 0 < div < 10^5 , that is, 1 <= div <= 99999 . The answer can be as large as 4999850001 (for n = div = 99999 ), which does not fit in a 32-bit signed integer. Use a 64-bit integer type ( long long in C++, long in Java). Examples Example 1 Input: 12 4 Output: 18 Explanation: The remainders of 1, 2, ..., 12 divided by 4 are 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0 ,