Subarray Sum Multiples
Given N integers, find the number of subarrays whose sum is a multiple of K. A subarray is a contiguous part of an array. The sum of an empty subarray is 0.
Input
The first line contains two integers N and K. The second line contains N space-separated integers a_1, a_2, ..., a_N.
Output
Print a single integer: the number of subarrays whose sum is a multiple of K.
Constraints
1 <= N <= 200000, 1 <= K <= 200000, -10^9 <= a_i <= 10^9
Example 1
5 3 4 5 0 -2 -3
6
Subarrays with sum multiple of 3 are: [0] (sum 0), [-2, -3] (sum -5, not mult of 3), [4, 5, 0, -2, -3] (sum 4, not mult of 3). Actually, prefix sums are: 0, 4, 9, 9, 7, 4. Remainders mod 3: 0, 1, 0, 0, 1, 1. Pairs with same remainder: (P[0]=0, P[2]=0), (P[0]=0, P[3]=0), (P[1]=1, P[4]=1), (P[1]=1, P[
Example 2
3 5 5 10 15
6
All subarrays have sums that are multiples of 5. There are 3*(3+1)/2 = 6 subarrays: [5], [10], [15], [5,10], [10,15], [5,10,15].
Hints
Similar problems
- Count Pairs with Digit Sum Divisible by KMedium
- Count Distinct Prefix SumsMedium
- Count Pairs with Equal XOR SumMedium
- Subarray Sums with Target DifferenceMedium
- Subsegment Sum Divisible by KMedium
- Pairs with Sum Divisible by KMedium
More topics: Hash Map and Hashing problems, Prefix Sums problems, Math and Number Theory problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 4 5 0 -2 -3
3 5 5 10 15