PROBLEM LINK:Author: Sarvesh Mahajan DIFFICULTY:MEDIUMHARD PREREQUISITES:InclusionExclusion,Mobius Function,Binary search PROBLEM:Define degree of a number is the highest power of a prime in its prime factorisation. A bobprime is a number having prime degree. Find kth smallest bobprime. 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 inclusionexlusion or mobius function. EXPLANATION:Let's convert the problem into a counting problem. Finding kth bobprime is same as finding the first x such that there as less than or equal to k bobprimes less than it. Therefore, we can do a binary search for this x and the problem turns into finding the number of bobprimes 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.
Note that we only need to iterate till primes<37 since 2^{37} > 10^{10}. 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. 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 nonzero 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 detailsWe can calculate all prime numbers <= $10^{5}$ using sieve of Erastothenes. Alternatively, if you are familiar with mobius function, you will notice that this inclusionexclusion is implicit in the definition of
mobius function.
We can calculate the values of mobius function for all numbers <=$10^{5}$ and then, AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 29 Sep '16, 20:05
