Encontre números de subarray de um array cuja soma é dividida pelo número dado
Eu fiquei preso em uma questão de algoritmo. Por favor me sugira algum algoritmo eficiente para o problema abaixo.
Questão é
Encontre números de submatrizes cuja soma é divisível por determinado número.
Meu trabalho
Eu fiz um algoritmo, cuja complexidade é O (N ^ 2), aqui, N = tamanho de um array.
Meu 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;
}