Programa C++ para productos de rangos en una array

Dada una array A[] de tamaño N. Resolver consultas Q. Encuentre el producto en el rango [L, R] bajo el módulo P (P es Prime). 

Ejemplos:  

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 

Fuerza bruta
Para cada una de las consultas, recorra cada elemento en el rango [L, R] y calcule el producto bajo el módulo P. Esto responderá cada consulta en O(N).  

// Product in range
// Queries in O(N)
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// Product in the given range.
int calculateProduct(int A[], int L,
                     int R, int P)
{
    // As our array is 0 based
    // as and L and R are given
    // as 1 based index.
    L = L - 1;
    R = R - 1;
 
    int ans = 1;
    for (int i = L; i <= R; i++)
    {
        ans = ans * A[i];
        ans = ans % P;
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int A[] = { 1, 2, 3, 4, 5, 6 };
    int P = 229;
    int L = 2, R = 5;
    cout << calculateProduct(A, L, R, P)
         << endl;
 
    L = 1, R = 3;
    cout << calculateProduct(A, L, R, P)
         << endl;
 
    return 0;
}

Producción :  

120
6

Eficiente usando el inverso multiplicativo modular:
como P es primo, podemos usar el inverso multiplicativo modular. Usando programación dinámica, podemos calcular una array de preproductos bajo el módulo P tal que el valor en el índice i contiene el producto en el rango [0, i]. De manera similar, podemos calcular el producto pre-inverso bajo el módulo P. Ahora cada consulta se puede responder en O(1). 
La array del producto inverso contiene el producto inverso en el rango [0, i] en el índice i. Entonces, para la consulta [L, R], la respuesta será Producto[R]*Producto inverso[L-1]
Nota: No podemos calcular la respuesta como Producto[R]/Producto[L-1] porque el producto es calculado bajo módulo P. Si no calculamos el producto bajo módulo P siempre existe la posibilidad de desbordamiento.  

// Product in range Queries in O(1)
#include <bits/stdc++.h>
using namespace std;
#define MAX 100
 
int pre_product[MAX];
int inverse_product[MAX];
 
// Returns modulo inverse of a
// with respect to m using
// extended Euclid Algorithm
// Assumption: a and m are
// coprimes, i.e., gcd(a, m) = 1
int modInverse(int a, int m)
{
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;
 
    if (m == 1)
        return 0;
 
    while (a > 1)
    {
 
        // q is quotient
        q = a / m;
 
        t = m;
 
        // m is remainder now,
        // process same as
        // Euclid's algo
        m = a % m, a = t;
 
        t = x0;
 
        x0 = x1 - q * x0;
 
        x1 = t;
    }
 
    // Make x1 positive
    if (x1 < 0)
        x1 += m0;
 
    return x1;
}
 
// calculating pre_product
// array
void calculate_Pre_Product(int A[],
                           int N, int P)
{
    pre_product[0] = A[0];
 
    for (int i = 1; i < N; i++)
    {
        pre_product[i] = pre_product[i - 1] *
                                        A[i];
        pre_product[i] = pre_product[i] % P;
    }
}
 
// Calculating inverse_product
// array.
void calculate_inverse_product(int A[],
                               int N, int P)
{
    inverse_product[0] = modInverse(pre_product[0], P);
 
    for (int i = 1; i < N; i++)
        inverse_product[i] = modInverse(pre_product[i], P);
}
 
// Function to calculate
// Product in the given range.
int calculateProduct(int A[], int L,
                     int R, int P)
{
    // As our array is 0 based as
    // and L and R are given as 1
    // based index.
    L = L - 1;
    R = R - 1;
    int ans;
 
    if (L == 0)
        ans = pre_product[R];
    else
        ans = pre_product[R] *
              inverse_product[L - 1];
 
    return ans;
}
 
// Driver Code
int main()
{
    // Array
    int A[] = { 1, 2, 3, 4, 5, 6 };
 
    int N = sizeof(A) / sizeof(A[0]);
 
    // Prime P
    int P = 113;
 
    // Calculating PreProduct
    // and InverseProduct
    calculate_Pre_Product(A, N, P);
    calculate_inverse_product(A, N, P);
 
    // Range [L, R] in 1 base index
    int L = 2, R = 5;
    cout << calculateProduct(A, L, R, P)
         << endl;
 
    L = 1, R = 3;
    cout << calculateProduct(A, L, R, P)
         << endl;
    return 0;
}

Producción :  

7
6

¡Consulte el artículo completo sobre Productos de rangos en una array para obtener más detalles!