The Busy Network
UptoSkills Arena's new server is experiencing high traffic. The network administrator has logged the data transfer (in MB) for each minute over a period of N minutes. They want to find out how many continuous periods of time (subarrays) resulted in a total data transfer that is a multiple of K MB. Help the administrator identify these periods.
Input
The first line contains two integers N and K (1 <= N <= 200000, 1 <= K <= 200000). The second line contains N space-separated integers representing the data transfer amounts for each minute (0 <= a_i <= 10^9).
Output
Print a single integer: the total number of continuous periods (subarrays) whose sum is divisible by K.
Constraints
1 <= N <= 200000 1 <= K <= 200000 0 <= a_i <= 10^9
Example 1
5 3 1 2 3 4 5
7
Subarrays are [3], [1, 2], [4, 5], [1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 2, 3, 4, 5] summing to 3, 3, 9, 6, 9, 12, 15. The sums divisible by 3 are 3, 3, 9, 6, 9, 12, 15. Count = 7. Wait, the correct sums are: [3]->3, [1,2]->3, [4,5]->9, [1,2,3]->6, [2,3,4]->9, [3,4,5]->12, [1,2,3,4,5]->15. Total 7.
Example 2
4 5 5 5 5 5
10
Subarrays are [5], [5], [5], [5], [5, 5], [5, 5], [5, 5], [5, 5, 5], [5, 5, 5], [5, 5, 5, 5]. All sums are multiples of 5. Count = 10.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 1 2 3 4 5
4 5 5 5 5 5