Ich steckte in einer Algorithmusfrage fest. Bitte schlagen Sie mir einen effizienten Algorithmus für das unten stehende Problem vor.

Die Frage ist

Finden Sie die Anzahl der Subarrays, deren Summe durch die angegebene Anzahl teilbar ist.

Meine Arbeit

Ich habe einen Algorithmus erstellt, dessen Komplexität O (N ^ 2) ist, hier N = Größe eines Arrays.

Mein Code

#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;
 }