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

×

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

This question is marked "community wiki".

asked 05 May '15, 18:48

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

edited 09 May '15, 15:31


good editorial.

link

answered 06 May '15, 02:15

sharru05's gravatar image

3★sharru05
5591723
accept rate: 14%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,722
×371
×14
×3

question asked: 05 May '15, 18:48

question was seen: 797 times

last updated: 09 May '15, 15:31