409765: GYM103736 F Subarrays

Give you an array of $$$n$$$ positive integers, your task is to count the number of subarrays whose sum is a multiple of $$$k$$$.

A subarray of array is a sequence $$$a_{l},a_{l+1},...,a_{r}$$$ for some integers $$$(l,r)$$$ such that $$$1\leq l \leq r \leq n$$$.

The first line contains two positive integers $$$n$$$ $$$(1\leq n \leq 10^{5})$$$, $$$k$$$ $$$(1\leq k \leq 10^{9})$$$.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \cdots, a_n$$$ $$$(0\leq a_i \leq 10^{9})$$$.

Output one line containing one integer indicating the number of subarrays.

6 3
0 1 2 4 7 7

7

For the test

$$$sum[1,1] = 0 $$$ , $$$0$$$ is a multiple of $$$3$$$

$$$sum[1,3] = 0 + 1 + 2 = 3$$$ , $$$3$$$ is a multiple of $$$3$$$

$$$sum[1,6] = 0 + 1 + 2 + 4 + 7 + 7= 21$$$ , $$$21$$$ is a multiple of $$$3$$$

$$$sum[2,3] = 1 + 2 = 3$$$ , $$$3$$$ is a multiple of $$$3$$$

$$$sum[2,6] = 1 + 2 + 4 + 7 + 7= 21$$$ , $$$21$$$ is a multiple of $$$3$$$

$$$sum[3,4] = 2 + 4 = 6$$$ , $$$6$$$ is a multiple of $$$3$$$

$$$sum[4,6] = 4 + 7 + 7 = 18$$$ , $$$18$$$ is a multiple of $$$3$$$

So the ans is $$$7$$$.