You are not logged in. Please login at to post your questions!



Problem Link :


Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu

Difficulty :




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.


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

This question is marked "community wiki".

asked 05 May '15, 18:48

dragonemperor's gravatar image

accept rate: 10%

edited 09 May '15, 15:31

good editorial.


answered 06 May '15, 02:15

sharru05's gravatar image

accept rate: 14%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 05 May '15, 18:48

question was seen: 797 times

last updated: 09 May '15, 15:31