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