# 數組中範圍的乘積

## 例

```arr[] = {1,2,3,4,5,6}

M = 131

Query = [1, 6], [2, 4]```
`65 24`

## 推薦碼

### C ++代碼在數組中查找範圍乘積

```#include <iostream>
using namespace std;
#define MAX 100

int PreProductArray[MAX];
int PreInverseProduct[MAX];

int InverseP(int a, int modulo)
{
int mP = modulo, temp, quotient;
int xP = 0, x = 1;

if (modulo == 1)
return 0;

while (a > 1)
{
quotient = a / modulo;

temp = modulo;

modulo = a % modulo;
a = temp;

temp = xP;

xP = x - quotient * xP;

x = temp;
}
if (x < 0)
x += mP;

return x;
}

void calculatePreProduct(int A[], int N, int P)
{
PreProductArray[0] = A[0];

for (int i = 1; i < N; i++)
{
PreProductArray[i] = PreProductArray[i - 1] *A[i];

PreProductArray[i] = PreProductArray[i] % P;
}
}
void calculatePreInverseProduct(int A[], int N, int P)
{
PreInverseProduct[0] = InverseP(PreProductArray[0], P);

for (int i = 1; i < N; i++)
PreInverseProduct[i] = InverseP(PreProductArray[i], P);
}
int calculateProduct(int A[], int L, int R, int P)
{
L = L - 1;
R = R - 1;
int ans;

if (L == 0)
ans = PreProductArray[R];
else
ans = PreProductArray[R] *
PreInverseProduct[L - 1];

return ans;
}

int main()
{
int Arr[] = { 1, 2, 3, 4, 5, 6 };

int N = sizeof(Arr) / sizeof(Arr[0]);

int Modulo = 131;
calculatePreProduct(Arr, N, Modulo);
calculatePreInverseProduct(Arr, N, Modulo);

int Left = 1, Right = 6;
cout << calculateProduct(Arr, Left, Right, Modulo) << endl;

Left = 2, Right = 4;
cout << calculateProduct(Arr, Left, Right, Modulo)
<< endl;
return 0;
}
```
```65
24```

### Java代碼在數組中查找範圍乘積

```class ProductInRange
{

static int MAX = 100;
static int PreProductArray[] = new int[MAX];
static int PreInverseProduct[] = new int[MAX];

static int InverseP(int a, int modulo)
{
int mP = modulo, temp, quotient;
int xP = 0, x = 1;

if (modulo == 1)
return 0;

while (a > 1)
{
quotient = a / modulo;

temp = modulo;

modulo = a % modulo;
a = temp;

temp = xP;

xP = x - quotient * xP;

x = temp;
}
if (x < 0)
x += mP;

return x;
}

static void calculatePreProduct(int A[], int N, int P)
{
PreProductArray[0] = A[0];

for (int i = 1; i < N; i++)
{
PreProductArray[i] = PreProductArray[i - 1] *
A[i];
PreProductArray[i] = PreProductArray[i] % P;
}
}

static void calculatePreInverseProduct(int A[], int N, int P)
{
PreInverseProduct[0] = InverseP(PreProductArray[0], P);

for (int i = 1; i < N; i++)
PreInverseProduct[i] = InverseP(PreProductArray[i],
P);
}

static int calculateProduct(int A[], int L, int R, int P)
{
L = L - 1;
R = R - 1;
int ans;

if (L == 0)
ans = PreProductArray[R];
else
ans = PreProductArray[R] *
PreInverseProduct[L - 1];

return ans;
}

public static void main(String[] args)
{

int Arr[] = { 1, 2, 3, 4, 5, 6 };

int Modulo = 131;
calculatePreProduct(Arr, Arr.length, Modulo);
calculatePreInverseProduct(Arr, Arr.length,
Modulo);
int Left = 1, Right = 6;
System.out.println(calculateProduct(Arr, Left,
Right, Modulo));
Left = 2;
Right = 4;
System.out.println(calculateProduct(Arr, Left,
Right, Modulo));

}
}
```
```65
24```

## 複雜度分析

### 時間複雜度

O（N log M + Q）， 此處的日誌M是因為找到乘積的逆。 然後用O（Q）回答查詢。