Divisible by d - MarisaOJ: Marisa Online Judge

You are given an integers array

$A$ of

$n$ elements. Count the number of subarray with sum divisible by

$d$ . A subarray is a contiguous sequence of elements within an array. For example, given an array

$B = [1, 2, 3, 4, 5]$ , array C =

$[2, 3, 4]$ is a subarray of

$B$ . ### Input - The first line contains 2 integers

$n, d$ . - The second line contains

$n$ integers

$A_i$ . ### Output - Print the number of subarray with sum divisible by

$d$ . ### Constraints -

$1 \le n, d \le 10^5$ . -

$|A_i| \le 10^9$ . ### Example Input:

$5 4 1 3 -2 3 -5$

Output:

$4$

Topic

Prefix sum

Rating

800

Solution (0)

Solution