C++程序数组中范围乘积

给定大小为N的数组A[]。解决Q个查询。在模P（P为质数）下找到范围[L，R]中的乘积。

示例：

输入：A[] = {1，2，3，4，5，6}
L = 2，R = 5，P = 229
输出：120

输入：A[] = {1，2，3，4，5，6}，
L = 2，R = 5，P = 113
输出：7

暴力法

对于每个查询，遍历[L，R]范围内的每个元素，并在模P下计算乘积。这将在O（N）中回答每个查询。

// 范围内的乘积
// 查询为O（N）
#include 
using namespace std;
 
// 计算给定范围内的乘积
int calculateProduct（int A[]，int L，
                     int R，int P）
{
    // 因为我们的数组是基于0的
    // 因为L和R是给出的
    // 作为1个基于索引。
    L = L - 1;
    R = R - 1;
 
    int ans = 1;
    for（int i = L; i <= R; i ++）
    {
        ans = ans * A [i];
        ans = ans ％ P;
    }
 
    返回答案;
}
 
// 驱动程序
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;
 
    返回0;
} ```

输出 :

120
6

高效使用 模意义下的乘法逆元：

由于P是质数，我们可以使用模乘法逆元。使用动态编程，我们可以在模P下计算预乘数组，使得索引i处的值包含范围[0，i]中的乘积。同样，我们可以计算模P下的预反转乘积。现在，每个查询都可以在O（1）中回答。
反转乘积数组在索引i处包含范围[0，i]中的倒数乘积。因此，对于查询[L，R]，答案将是Product[R] * InverseProduct [L-1]

注意：我们无法像Product[R]/Product[L-1]那样计算答案，因为在模P下计算乘积。如果我们不在模P下计算产品，就始终存在溢出的可能性。

// 在O(1)中查询一定范围内的乘积
#include <bits/stdc++.h>
using namespace std;
#define MAX 100
 
int pre_product[MAX];
int inverse_product[MAX];
 
// 使用扩展欧几里得算法返回相对于m的a的模反元素
// 假设：a和m是互质的，即：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是商
        q = a / m;
 
        t = m;
 
        // m现在是余数，
        // 处理方式与
        // 欧几里得算法相同
        m = a % m, a = t;
 
        t = x0;
 
        x0 = x1 - q * x0;
 
        x1 = t;
    }
 
    // 使x1为正数
    if (x1 < 0)
        x1 += m0;
 
    return x1;
}
 
// 计算pre_product的函数
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;
    }
}
 
// 计算inverse_product的函数。
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);
}
 
// 计算给定范围内的乘积的函数。
int calculateProduct(int A[], int L,
                     int R, int P)
{
    //由于数组是以0为基础的，因此我们要求得的L和R给定为1
    //基础索引。
    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;
}
 
//驱动程序
int main()
{
    // 数组
    int A[] = { 1, 2, 3, 4, 5, 6 };
 
    int N = sizeof(A) / sizeof(A[0]);
 
    // 素数P
    int P = 113;
 
    // 计算PreProduct和InverseProduct
    calculate_Pre_Product(A, N, P);
    calculate_inverse_product(A, N, P);
 
    // 1-based索引中的范围[L，R]
    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;
}