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

×

IITM4 - Editorial(IITM2016)

PROBLEM LINK:

Practice

Contest

Author: Hitesh Ramchandani

Tester: Sagar Gupta

Editorialist: Hitesh Ramchandani

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

Math, Sieve-of-eratosthene­s

PROBLEM:

A good number is a number whose count of divisors is greater than the count of divisors for all the numbers less than it. You have to find number of good numbers between two integers L and R(inclusive).

QUICK EXPLANATION:

These good numbers are called highly composite numbers. Let N = 2^a2 * 3^a3 * 5^a5 ... p^ap (ie prime factorization of N ). A number N is a good number if :

  1. The primes 2, 3, 5 .. p form consecutive primes in its factorization.
  2. The exponents are non-decreasing a2 ≥ a3 ≥ a5 .. ≥ ap.
  3. The final exponent ap = 1, except for 2 cases when N = 4 (2^2) and N = 36 (2^2*3^2).

EXPLANATION:

Naive approach(Subtask #1 30 pts):

Calculate all divisors of a number and store it which takes O(summation over i from 1 to n root(i)). This is sufficient for 30 points and will fail for larger test cases.

Subtask #2(70 pts):

To answer the problem, we need to compute if a number N is good or not (or in other words highly composite). For this we need to calculate prime factorization of N. To calculate Prime factorization of N efficiently, we use Sieve-of-eratosthene­s which calculates prime numbers from 1 to N in O(Nlog^2(n)). So we first precompute all the prime numbers upto 10^7 using Sieve-of-eratosthene­s. Now for every N, we check if it satisfies the above conditions and also keep a count of number of divisors using the formula : num of divisors = (a2+1)(a3+1)*(a4+1)­...(ap+1).

Now consider N = 30 (2.3.5), it satisfies the above conditions but is still not a good number because N = 24 (2^3*3) also has 8 divisors. So it is necessary to store this information that number of divisors of 24 is 8 and thus even though 30 satisfies the above conditions, it is not a good number.

Precompute and store if N is good or not for all N's from 1 to 10^7.

TIME COMPLEXITY:

O(N*log^2(N))

ALTERNATIVE APPROACH:

The number of good numbers upto 10^7 is just 48. One can hardcode those numbers and solve the problem.

TIME COMPLEXITY:

O(1)

This question is marked "community wiki".

asked 12 Dec '16, 16:37

hitman_coder's gravatar image

5★hitman_coder
41
accept rate: 0%

edited 12 Dec '16, 16:49

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:

×3,820
×303
×57

question asked: 12 Dec '16, 16:37

question was seen: 454 times

last updated: 12 Dec '16, 16:49