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

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

输出:

7
6

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例