Subsegment Sum Divisible by K
Given an array of N integers and an integer K, find the number of non-empty subsegments whose sum is divisible by K. A subsegment is a contiguous part of the array. For example, in the array [1, 2, 3, 4], [2, 3] is a subsegment, but [1, 3] is not.
Input
The first line contains two integers N and K. The second line contains N integers, the elements of the array.
Output
Print a single integer: the count of subsegments whose sum is divisible by K.
Constraints
1 <= N <= 200000 1 <= K <= 200000 -10^9 <= a[i] <= 10^9
Example 1
5 3 4 5 0 -2 -3
6
Subsegments with sum divisible by 3 are: [5, 0, -2, -3] (sum -0), [0] (sum 0), [-2, -3] (sum -5, not divisible), [4, 5] (sum 9), [5, 0, -2] (sum 3), [0, -2, -3] (sum -5, not divisible). Correct subsegments: [4, 5], [5, 0, -2], [0]. Wait, the prefix sum logic is tricky. The subsegments are: [4,5] sum
Example 2
3 5 1 2 3
1
No subsegment sum is divisible by 5.
Hints
Similar problems
- Count Pairs with Equal XOR SumMedium
- Sum of Distinct ElementsMedium
- Count Distinct Prefix SumsMedium
- Count Pairs with Digit Sum Divisible by KMedium
- String PartitionMedium
- Count Subarrays with Target Sum DifferenceMedium
More topics: Hash Map and Hashing problems, Prefix Sums problems, Recursion 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 1 2 3