PROBLEM LINK:
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.