# 1. Problem Understanding In this problem, we are given an array of integers and a "mystical divisor" $K$. Our task is to count the number of contiguous subarrays whose sums are divisible by $K$. A subarray is any continuous segment of the array. For example, given an array $[a_1, a_2, \dots, a_N]$, a subarray could be defined by indices $i$ and $j$ such that the subarray is $[a_i, a_{i+1}, \dots, a_j]$. The sum of this subarray is $S_{i,j} = \sum_{k=i}^j a_k$. The condition for a subarray to be "mystical" is that $S_{i,j} \mod K = 0$. There might be multiple test cases in a single input. # 2. Solution Analysis A brute force approach to solve the problem would involve iterating over all possible subarrays and computing their sum, then checking for divisibility by $K$. However, since the number of subarrays in an array of size $N$ is on the order of $\mathcal{O}(N^2)$, and computing each sum in a naive manner may also take linear time, this brute force approach becomes inefficient for large arrays. A more efficient approach leverages **prefix sums** and the properties of the modulo operation. Here’s the outline of the algorithm: - Compute a prefix sum array, where $P[i] = \sum_{j=0}^{i} a_j$. - For any subarray defined by indices $i$ and $j$ (with $i \leq j$), the subarray sum can be expressed as $P[j] - P[i-1]$. - The key observation is that the subarray sum $S_{i,j}$ is divisible by $K$ if and only if: $$ (P[j] - P[i-1]) \mod K = 0 \quad \Longleftrightarrow \quad P[j] \mod K = P[i-1] \mod K $$ - We can count how many times each remainder (after taking modulo $K$) appears while iterating through the prefix sum array. - If a particular remainder $r$ appears $n_r$ times, then there are $\frac{n_r \times (n_r - 1)}{2}$ pairs of indices (i.e., subarrays) that give a sum divisible by $K$. - Additionally, whenever the prefix sum itself is divisible by $K$ (i.e., remainder $0$), it means that the subarray from the beginning of the array to that point is mystical. This method avoids explicitly checking every subarray, reducing the time complexity significantly. # 3. Time and Space Complexity Analysis - **Time Complexity:** - Calculating the prefix sum by iterating through the array takes $\mathcal{O}(N)$ time. - Iterating over the prefix sums to count modulo frequencies also takes $\mathcal{O}(N)$ time. - Thus, the overall time complexity per test case is $\mathcal{O}(N)$. - **Space Complexity:** - Storing the prefix sums requires $\mathcal{O}(N)$ space. - The frequency dictionary (or array) used to count remainders takes $\mathcal{O}(K)$ space. - In total, the space complexity is $\mathcal{O}(N + K)$ per test case. # 4. Implementation Details - Read the input, taking into account multiple test cases. - For each test case: - Parse the values of $N$ and $K$, and then the array of integers. - Initialize a variable for the running prefix sum. - Use a dictionary (or an array of size $K$) to maintain the count of each prefix sum modulo $K$. Initially, set the count for remainder $0$ to be $1$, as having a prefix sum exactly divisible by $K$ on its own (from index $0$ to some $i$) is valid. - As you iterate through the array: - Update the running prefix sum. - Compute the current remainder, ensuring it is non-negative (using modulo $K$ properly). - Add the count of the current remainder (from the dictionary) to the answer because each matching earlier prefix signifies a subarray with a sum divisible by $K$. - Increment the count for the current remainder. - Finally, output the count for mystical subarrays for each test case. This solution is efficient enough to handle large inputs within the problem constraints without resorting to a brute force technique.