Problem Link :Author: Amrutansu Garanaik , Abhishek Patnaik Difficulty :easymedium PrerequisiteBITProblem :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.ExplanationThe 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.
See Setter solution for implementation
This question is marked "community wiki".
asked 05 May '15, 18:48
