Subarrays With Sum Divisible by K
mediumArrays & Prefix Sums+20 XPTime limit 2s
Count the non-empty contiguous subarrays whose sum is divisible by k. (A sum of 0 counts — it is divisible by every k.)
Input:
- line 1:
n k - line 2:
nintegers (may be negative)
Output: the number of such subarrays (it can exceed 2³¹ — use 64-bit integers).
Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁴, −10⁴ ≤ a[i] ≤ 10⁴.
Think about it: a[l..r] is divisible by k exactly when the prefix sums at l − 1 and r leave the same remainder mod k. Count remainders in a map as you go. Careful: in C++/Java/JS, % of a negative number is negative — use ((x % k) + k) % k.
Sample input 1
6 5 4 5 0 -2 -3 1
Sample output 1
7
Sample input 2
1 9 5
Sample output 2
0
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).