### PROBLEM LINKS

### DIFFICULTY

EASY

### PREREQUISITES

Simple Math, Repeated Squaring

### PROBLEM

You are given a list of N integers.

Each value in the list is between 1 and 100.

You have to respond to T queries of the following type

- Given L and R
- Find the product of all integers in the given list between L and R, inclusive
- Find the above product modulo some M, which is also given

### EXPLANATION

For each query, iterating through the list between **L and R** to maintain the **modular products** is too slow.

Of course, we use the fact that each value is between **1 and 100** to our advantage.

- There are
**25 prime numbers between 1 and 100**

Each number has a unique prime factorization. The product of a set of numbers can also be simulated by adding up the frequencies of each prime in all numbers in the set.

For example, suppose we have to multiply 36 and 45.

36 = 2^{2}3^{2}45 = 3^{2}5 36 * 45 = 2^{2}3^{4}5

Thus, we can maintain a table of **cumulative frequencies for each of the 25 primes between 1 to 100** for the given list of numbers.

When processing a query

- consider each of the 25 primes
- find the
**frquency of the prime between L and R**. This can be done in O(1) using**pre-calculation of cumulative frequencies** - calculate
**prime**for each prime and multiply these values^{frquency} - maintain the result
**modulo M**

These ideas are best presented in the pseudo code below.

### PSEUDO CODE

Given: N, the number of numbers L[N], the list of numbers P[25], primes between [1, 100] CF[N,25], cumulative frquency for each prime for each query Given Query: left, right, M answer = 1 for i = 1 to 25 r = CF[right,i] - CF[left-1,i] v = P[i]^{r}% M, use repeated squaring answer = (answer * v) % M

The complexity of answering each query would be **O(25 log N)**.

Cumulative Frequencies can be calculated in **O(25 * N)**.

### CODING COMMENTARY

You can either calculate the primes in thr porgram or hard code the array of primes by calculating it offline.

The repeated squaring should take care of the fact that the exponent can be 0. **a ^{0}** should return 1 for any

**a**.

Calculating the cumulative frequencies table should be done carefully. The frequencies of the primes for each number between **1 and 100** can be **pre-calculated**. Use these frequencies to build the cumulative frequencies table.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.