## Editorial for DMOPC '17 Contest 1 P2 - Sharing Crayons

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

For the first subtask, we can loop through all subarrays and find their sum, and count how many are divisible by .

**Time Complexity:**

For the second subtask, we can iterate through all subarrays and find their sum using a prefix sum array, and count how many are divisible by .

**Time Complexity:**

Let .

For the third subtask, notice that the sum of a subarray will be divisible by if . Thus we can store a counter array of size such that the th entry is the number of prefix sums that are congruent to mod . Thus we can just loop through , and add to our answer, and then increment it by one.

**Time Complexity:**

For the fourth subtask, we can replace the counter array with a map data structure, as an array of size will MLE.

**Time Complexity:**

**Extra Challenge:** Can you solve this problem without using a map data structure?

## Comments