Problem Link :
Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu
Difficulty :
easy-medium
Pre-requisite BIT ## Problem : Given an array of numbers and some queries of the form (i,j), you have to print the product of the numbers in the interval [i,j] and find the number of factors of the number obtained after multiplication. ## Explanation
The numbers in the array are less than 100. Number of primes below 100 is 25. So we can store the prime factors of each number easily. Then we can use a binary index tree to store the prefix sum of each prime factors in the array. Then to find the multiplication in an interval, we need to find all the prime factors in the interval and multiply them. On each multiplication, we need to find the modulus to get the correct result.
For finding the number of factors, we have the prime factors in the interval. Let the prime factors in the interval be p1,p2,…,pn and each prime number is present a1,a2,…,an times respectively. So the number of factors is given by the formula
See Setter solution for implementation