Mr IDC and his Love - Editorial

PROBLEM LINK:

Practice

Contest

Author: Rahul Johari

Tester: Rahul Johari

DIFFICULTY:

EASY-MEDIUM, MATHS

PREREQUISITES:

Division, Summation of series, modular operation

PROBLEM:

Given a number N and another number MOD, you have to calculate the sum of numbers from 1 to N as:

for ( i=1;i<=N;i++ )
	sum += i % MOD;

EXPLANATION:

By the division algorithm, let N = qm+r with 0 ≤ r < m. Consider the sequence
(1 m),(2 m), …,(N % m). It looks like this:

1, 2, 3, ..., m − 1, 0,
1, 2, 3, ..., m − 1, 0,
...
1, 2, 3, ..., m − 1, 0,
1, 2, 3, ..., r

There are q layers, each with m elements and a final layer with r elements.

We know that sum of first N terms is N(N+1)/2 therefore the sum the numbers in
each of the q layers is m(m−1)/2 and the sum of the numbers in the last layer is r(r+1)/2.

Therefore using this you can easily calculate sum of large values of N also is O(1) complexity.

AUTHOR’S AND TESTER’S SOLUTIONS:

Solution can be found here.