BIGOF05-Editorial

Problem Link :

Contest Practice

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

p1^a1 * p2^a2 * ... * pn^an

See Setter solution for implementation

good editorial.