Программа Javascript для продуктов диапазонов в массиве

Опубликовано: 2 Сентября, 2022

Дан массив A[] размера N. Решите Q запросов. Найдите произведение в диапазоне [L, R] по модулю P (P — простое число).

Примеры:

Input : A[] = {1, 2, 3, 4, 5, 6} 
          L = 2, R = 5, P = 229
Output : 120

Input : A[] = {1, 2, 3, 4, 5, 6},
         L = 2, R = 5, P = 113
Output : 7 

Грубая сила
Для каждого из запросов пройдите каждый элемент в диапазоне [L, R] и вычислите произведение по модулю P. Это даст ответ на каждый запрос за O (N).

Выход :

120
6

Эффективное использование модульной мультипликативной инверсии:
Поскольку P простое число, мы можем использовать модульную мультипликативную обратную. Используя динамическое программирование, мы можем вычислить массив предварительных произведений по модулю P так, чтобы значение с индексом i содержало произведение в диапазоне [0, i]. Точно так же мы можем вычислить предварительно обратный продукт по модулю P. Теперь на каждый запрос можно ответить за O (1).
Массив обратного произведения содержит обратное произведение в диапазоне [0, i] с индексом i. Итак, для запроса [L, R] ответом будет Product[R]*InverseProduct[L-1].
Примечание. Мы не можем вычислить ответ как Product[R]/Product[L-1], потому что произведение вычисляется по модулю P. Если мы не вычисляем произведение по модулю P, всегда существует вероятность переполнения.

Выход :

7
6

Пожалуйста, обратитесь к полной статье о продуктах диапазонов в массиве для получения более подробной информации!