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

×

BOBPRIME - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sarvesh Mahajan
Tester: Sai Sandeep

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Inclusion-Exclusion,Mobius Function,Binary search

PROBLEM:

Define degree of a number is the highest power of a prime in its prime factorisation. A bob-prime is a number having prime degree. Find kth smallest bob-prime.

QUICK EXPLANATION:

Binary search for the answer. Denote f(x,deg) as the number of numbers <= x , having degree >= deg. f(x,deg) can be found using inclusion-exlusion or mobius function.

EXPLANATION:

Let's convert the problem into a counting problem. Finding kth bob-prime is same as finding the first x such that there as less than or equal to k bob-primes less than it. Therefore, we can do a binary search for this x and the problem turns into finding the number of bob-primes less than a given number. The problem constraints guarantee that the answer is always < $10^{10}$. So this can be the upper limit for the binary search.
Let's say we have a function g(x,deg) which returns the number of numbers<=x having degree=deg. Then we can use the following pseudo-code to calculate the answer.

def get(x): # Returns number of bob-primes<=x for(p in primes): ret+=g(x,p) return ret

Note that we only need to iterate till primes<37 since 237 > 1010. Now the problem remains how to calculate g(x,deg).

Calculating g(x,deg):

Let f(x,deg) return the number of numbers<=x having degree>=deg.
Then clearly g(x,deg)=f(x,deg+1)-f(x,deg).
f(x,deg) can be calculated by inclusion exclusion. We add the count of numbers<=x divisible by ${2^{deg}},{3^{deg}},{5^{deg}},{7^{deg}} $ and so on. But we are overcounting here. So we subtract the count of numbers<=x divisible by ${2^{deg}}{3^{deg}} etc.$

Therefore, f(x,deg)= $\lfloor{\frac{x}{2^{deg}}}\rfloor + \lfloor{\frac{x}{3^{deg}}}\rfloor + \lfloor{\frac{x}{5^{deg}}}\rfloor + ...- \lfloor{\frac{x}{2^{deg}3^{deg}}}\rfloor-\lfloor{\frac{x}{2^{deg}5^{deg}}}\rfloor- .... + \lfloor{\frac{x}{2^{deg}3^{deg}5^{deg}}}\rfloor... $

Note that the denominator grows very fast so the number of non-zero terms is relatively small. Also note that since deg>=2, we only need to consider primes till $10^{5}$, as any number greater than this will contribute only a zero term in the answer.

Implementation details

We can calculate all prime numbers <= $10^{5}$ using sieve of Erastothenes.
We can generate the terms in denominator using recursion and prune the recursion tree by stopping when the denominator exceeds x. Also pre-compute values of prime powers<37. Refer author's solution for details.

Alternatively, if you are familiar with mobius function, you will notice that this inclusion-exclusion is implicit in the definition of mobius function. We can calculate the values of mobius function for all numbers <=$10^{5}$ and then,
f(x,deg)= $ - \sum_{y=2}^{10^{5}} \mu (y) *(x/y^{deg})$.
For details regarding calculation of mobius function refer tester's solution.
Time Complexity: Let max denote the bob-prime corresponding to the largest value of k. Then time complexity is $O(T*log(max)*sqrt(max))$

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 29 Sep '16, 20:05

sarveshmahajan's gravatar image

3★sarveshmahajan
115
accept rate: 0%

edited 20 Mar, 22:18

admin's gravatar image

0★admin ♦♦
17.4k347487515

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:

×12,344
×452
×64
×47

question asked: 29 Sep '16, 20:05

question was seen: 1,024 times

last updated: 16 Sep, 10:40