Найти номера подмассива массива, сумма которого делится на данное число

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

Для данного номера X…

Основная идея: (с неофициальным доказательством правильности)

Если сумма чисел в диапазоне [a, b] делится на X, затем:

(∑i=1 to a-1input[i]) % X = (∑i=1 to binput[i]) % X

В менее математических терминах:

the sum from the first element to b = the sum from the first element to a
+ the sum of the elements between the two

Так:

the sum of the elements between the two = the sum from the first element to b
- the sum from the first element to a

Затем, если эти суммы справа имеют одинаковый остаток при делении на X, остатки отменится, и сумма элементов между ними будет делиться на X, Разработка:

C = the sum of the elements between the two
B = the sum from the first element to b
A = the sum from the first element to a

Теперь мы можем конвертировать B к форме PX + Q а также A к форме RX + Sдля некоторых целых P, Q, R а также S, с 0 <= Q, S < X, Здесь по определению Q а также S будут соответствующие остатки B а также A делится на X,

Тогда мы имеем:

C = (PX + Q) - (RX + S)
C = PX + Q - RX - S
C = PX - RX + Q - S
C = (P-R)X + Q - S

очевидно (P-R)X делится на X (результат просто (P-R)). Теперь нам просто нужно Q - S делиться на X, но с тех пор 0 <= Q, S < X, они должны быть равны.

Пример:

Позволять B = 13, A = 7, X = 3,

Вот B % X = 1 а также A % X = 1,

Мы можем переписать B как 4*3 + 1 а также A как 2*3 + 1,

затем C = 4*3 + 1 - 2*3 - 1 = 2*3, который делится на 3,

Подход высокого уровня:

Построить хэш-карту key -> valueгде каждое значение представляет, сколько способов вы можете начать с начала массива и в конечном итоге в какой-то заданной позиции, которая складывается в sum mod X = key (см. строку «Мод 3» и значения карты в примере ниже).

Теперь, основываясь на логике выше, мы знаем, что если два подмассива начинаются с начала и заканчиваются в позициях a а также b соответственно оба имеют одинаковые sum mod XПодмассив [a, b] будет делиться на X,

Таким образом, каждое значение в хэш-карте представляет размер набора возможных начальных и конечных точек, которые дадут нам подмассив, делимый на X (любая точка может быть либо начальной, либо конечной точкой).

Количество возможных способов выбора этих начальных и конечных точек просто
value choose 2 = value!/(2*(value-2)!) (или 0, если значение равно 1).

Таким образом, мы вычисляем это для каждого значения в хэш-карте и складываем их все, чтобы получить количество подмассивов, делимых на X,

Алгоритм:

Построить хэш-карту, которая будет хранить совокупную сумму всех чисел к настоящему времени mod X отображается на счет того, как часто появляется это значение остатка (построено в ожидаемом O(n)).

Увеличение 0Значение по одному — это соответствует началу массива.

Инициализируйте счет до 0.

Для каждого значения в хэш-карте добавьте value!/(2*(value-2)!) на счет.

Количество является желаемым значением.

Продолжительность:

ожидаемый O(n),

Пример:

Input:    0  5  3  8  2  1
X = 3

Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

Map:
0 -> 3
1 -> 2
2 -> 2

Count = 3! / 2*(3-2)! = 3  +
2! / 2*(2-2)! = 1  +
2! / 2*(2-2)! = 1
= 5

Подмассивы будут:

0  5  3  8  2  1
-                     0                 =  0 % 3 = 0
-------------         0 + 5 + 3 + 8 + 2 = 18 % 3 = 0
----------         5 + 3 + 8 + 2     = 18 % 3 = 0
-               3                 =  3 % 3 = 0
----      2 + 1             =  3 % 3 = 0

#include <iostream>
#include <string.h>

using namespace std;

void printrange(int* A, int N, int K)
{
int STN[N], C[K];
memset(C, -1, K*sizeof(int));
int i;
int sum=A[0];
STN[0]= (A[0]%K);
for (i= 1; i< N; i++)
{
sum+= A[i];
STN[i]= sum%K;
}
for(i=0; i< N; i++)
{
if(C[STN[i]] == -1)
C[STN[i]] =i;
else
{
cout<< C[STN[i]]+1 <<" "<< i;
break;
}
}
}

int main()
{
int A[]= {6, 9, 2, 1, 8, 6, 2, 5};
printrange(A, sizeof(A)/sizeof(A[0]), 7);
return 0;
}