MISNUM - Editorial (NPLTZ15)

PROBLEM LINK:

Contest

Author: Saumyajit Dey
Tester: Devamanyu Hazarika
Editorialist: Devamanyu Hazarika

DIFFICULTY:

EASY

PREREQUISITES:

Math

PROBLEM:

The problem states that all the numbers which have exactly two divisors (greater than 1) have been deleted. Now ,you have to answer the count of missing numbers in a given range.

EXPLANATION:

We can easily figure out that a number is marked as many times as the divisors(greater than 1) of that number.

Now all missing numbers are basically square of prime numbers which will have only two divisors that is itself and its square root.

The task remains to identify the count of such numbers in a given a range. This can be easily done by generating prime numbers upto 105 using “Seive of Erastosthenes” and then squaring the prime numbers to get square of primes.

Now given any query, we can use binary search to find the indices of the smallest and largest square primes that lie in the given range (let it be i and j). Then the answer for the query will be j-i+1. Time complexity for each query is O(logk), where k is the number of square primes upto 109, which comes up to be in the order of 4 * 104.

AUTHOR’S AND TESTER’S SOLUTIONS:

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

RELATED PROBLEMS:

why i am getting wa?
https://www.codechef.com/viewsolution/8591033

The maximum value of prime in your precomputed array is less than 10^4
But here maximum value is 10^9 so you have to compute all the primes lesser than square root of 10^9 i.e. 31622

1 Like

got it. thanks

//