Me quedé atrapado en una pregunta de algoritmo. Por favor, sugiérame un algoritmo eficiente para el siguiente problema.

La pregunta es

Encuentra números de subarrays cuya suma es divisible por un número dado.

Mi trabajo

Hice un algoritmo, cuya complejidad es O (N ^ 2), aquí, N = tamaño de una matriz.

Mi código

#include<stdio.h>

using namespace std;

 main() {
    int N;
    int P;
    int T;
    int val;
    long long int count = 0;
    long long int answer = 0;
    scanf("%d", &T);
    //T = 20;

    for(int k = 1; k <= T; k++) {
        scanf("%d", &N);
        scanf("%d", &P);
        count = 0;
        answer = 0;
        for(int i = 0; i < N; i++) {
            scanf("%d", &val);
            count += val;
            workingArray[i] = count;
        }

        for(int length = 1; length <= N; length++) {
            for(int start = 0; start <= (N-length); start++) {
                if( start == 0 ) {
                    if(workingArray[start+length-1]%P == 0) answer++;
                }
                else if( (workingArray[start+length-1] - workingArray[start-1])%P == 0) answer++;
            }
        }

        printf("Case #%d\n%lld\n", k, answer);
    }
    return 0;
 }