Znajdź numery podwarstwy tablicy, której suma jest podzielona przez podaną liczbę
Utknąłem w jednym pytaniu algorytmu. Podaj mi jakiś skuteczny algorytm dla poniższego problemu.
Pytaniem jest
Znajdź liczby podzespołów, których suma jest podzielna przez podaną liczbę.
Moja praca
Zrobiłem jeden algorytm, którego złożoność to O (N ^ 2), tutaj N = rozmiar tablicy.
Mój kod
#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;
}