Problem

We are asked to find the number of subarrays that are divisible by $N$. In other words, we're supposed to find the number of subarrays with sum equal to $0 \pmod N$.

Explanation

Notice that any sum of a subarray can be represented as the difference of two prefixes.

First, let $\texttt{sum}$ represent the prefix sum of array $a$ modulo $N$.

With our prefix sums knowledge,

Since we want to calculate the number of $\texttt{sum}(i, j)$ that equals to $0\pmod N$, $\texttt{sum}(0, j)$ must be equal to $\texttt{sum}(0, i-1)$ for their difference to be $0$.

Now, we calculate $\texttt{pmod}[i]$, the number of prefixes with remainder equivalent to $i\pmod{N}$. Then the number of pairs contributed by $i$ is

The answer is just the sum of this quantity over all $i$.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <iostream>
#include <vector>

using namespace std;

/**
 * @author Qi Wang
 * (detemplifying courtesy of Kevin Sheng)
 */
int main() {

Copy
import java.io.*;
import java.util.*;

public class subarrayDivisibility {
	public static void main(String[] args) {
		Kattio io = new Kattio();

		int n = io.nextInt();

		long[] M = new long[n];

Copy
n = int(input())
arr = map(int, input().split())

residue_counts = [0] * n
partial_sum = 0
residue_counts[partial_sum] = 1
for a in arr:
	partial_sum += a
	partial_sum = partial_sum % n
	residue_counts[partial_sum] += 1

# each subarray with sum divisible by n corresponds to
# a pair of indices that have the same residue
print(sum(r * (r - 1) // 2 for r in residue_counts))