Divisible Subarray Sums

Difficulty: 1500 3000 ms 128 MB

math prefix-sums

Count the contiguous subarrays whose sum is divisible by K.

Input: the first line has N and K; the second line has N integers.

Output: the number of subarrays with sum ≡ 0 (mod K).

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ 100
• |a_i| ≤ 100

Sample Tests

5 5
4 5 0 -2 -3

6

2 2
1 1

1

Read the Editorial