PROBLEM LINK:
Author-
Tester-
Editorialist- Abhishek Pandey
DIFFICULTY
Easy
PRE-REQUISITES
Sieve of Eratosthenes , Sorting, Binary Search
PROBLEM
Given an array of N numbers, we have to find and print the overall ranking of supporters of the move. The rank must be in ascending order.
QUICK EXPLANATION
The main body of the problem is finding if number of divisors of P is an odd prime number or not. We first notice, that for number of divisors to be a prime number, the number P must be of form P= {a}^{b} , where a is a prime number. Also, due to this, there are only some values of P possible in range [1,{10}^{12}] which can be supporters. Hence, we store all the possible values of {P} (which are supporters) in an array/vector. Now, for every element in the (sorted) input array, we do a Binary search (in supporter’s array) to check if its a supporter or not. If a value is found, it means {P_i} is supporter.
EXPLANATION
While reading the question, the very first thing coming to almost everyone’s mind is same. That-
I will run a sieve, store the least prime dividing the number, and hence, factorize it and check if number of divisors are prime or not.
But this approach gets an immediate setback on the first look at constraints. {P_i} can be as large as {10}^{12} !!
Again, as I always emphasize, tackling any question head-on is not the best idea. Let us first give some in thinking. The question has specifically stated that for a person to be a supporter, {P_i} must have an odd-prime number of divisors. Its always fruitful to see the reason why setter takes pains to mention such small details!
Let us first write P in prime factorization form, and see if we can make an observation to solve this problem!
Let-
P_i= {p_1}^{a} * {p_2}^{b} * ....{p_i}^{k} , where {p_1}{p_2}...{p_i} are prime numbers dividing it, and a,b...k are their respective exponents.
We know by the high school formula, that number of divisors for {P_i} will be (a+1)*(b+1)*...(k+1) .
Wait right there! Recall that our aim is see if number of divisors of {P_i} is an odd prime number or not. We ought to ask ourselves a question now, that, are number of divisors of {P_i} prime?
No! The number of divisors of {P_i} is, in fact, divisible by (a+1), (b+1) ,..., (k+1). Essentially, we notice one crucial fact, that, if {P_i} is divisible by more than 1 prime number, then the number of its divisors will always be a product of 2 numbers (both greater than 1) and hence never prime.
The above observation puts a very neat restriction, that {P_i} must be expressible only in form of {P_i}= {p_1}^{a} . More formally, we can say that {P_i} must be a power of of prime. The number of divisors will then be (a+1), which can be prime. Also note, that {P_i} cannot be a prime number either, since prime numbers have exactly 2 divisors, which is not an odd prime number. This means, that a must be greater than 1. The minimum value of a is 2.
Now we can use our initial approach of sieve!
IMPLEMENTATION:
First, we make a simple sieve to find and store all prime numbers upto {10}^{6} . We choose our upper bound of {10}^{6} as, after this, {p_i}^{a} becomes greater than {10}^{12}, and hence out of concerned range.
We make another array/vector to store all possible {P_i} which are supporters.
Now, for every prime number we stored, we keep on increasing its power (i.e. a) by 1 till {p_i}^{a} gets out of range (i.e. greater than {10}^{12} ). And, if we find that (a+1) is prime, we store {p_i}^{a} in the newly created array. We can check if (a+1) is prime by using pre-computations from our initial sieve.
From now, the problem becomes really simple. We first sort the array so elements are in their respective positions/ranks and set our counter variable to 0 . We then start from the largest element (as ranks must be in ascending order). We check if {P_i} is a supporter or not, by checking its presence in our previously created vector/array. We can do the search in O(logN) time by using Binary search. Alternatively, we can use in-built functions of the language (if any) so that we can avoid writing code for Binary search. For every supporter we come across, we increase our counter. If {P_i} is a supporter, we can easily find its rank from its index in array.
If counter variable is 0 after iterating through the entire array, it means that there are no supporters and we print No supporter found.
Time Complexity: The code works in O(Klog[log(K)] + NlogP) complexity, where K= {10}^{6} (complexity of sieve) and P= size of array/vector with all supporters.
SOLUTION
COMMON SCOPE OF MISTAKES
Are you still getting WA after reading this editorial? Make sure you haven’t committed one of the common errors given below-
1.Overflow in sieve- Look at the pseudo code below.
for(int i=2;i<=1000000;i++)
{
for(int j=i*i;j<=1000000;j++)
Can you spot the error in it? Both i and j are int, and when i gets larger, j= i*i starts overflowing. Also, just declaring j as long long wont do. You must explicitly typecast the product to higher data type. The correct inner loop is given below-
for(long long j=(long long int)i*i;j<=1000000;j++) OR for(int j=2*i;j<=1000000;j++)
2.Printing No supporter found instead of No supporter found. Notice the full stop.
3.Incorrect code for Binary search.
4.Silly errors like unintialized loop variable, assuming wrong order of sorting (thinking elements are sorted in descending order when they are sorted in ascending order)
5.Using int instead of long long (i.e. 32 bit data type instead of 64bit) when computing possible {P_i}
6.Wrong calculation of rank via index/loop variable.
RELATED PROBLEMS
Noldback Problem - Quite Easy.
Almost Prime
Chef and Divisor Tree - This one is Medium level problem. You don’t need any knowledge of trees to solve this (don’t get deceived by its name!) but you need to know an extension of sieve, i.e. Segmented Sieve .
CHEF VIJJU’S CORNER 
1.The Binary Search part can be coded very quickly if you know the in-built functions for your language. C++ users can use the function lower_bound and quickly check the presence of element in supporter’s array. In a short contest, every second matters. Especially if you have a habit of making mistakes, because debugging can take some time!
2.What do you think about the Q if {P_i} would be {10}^{15}? {10}^{18} ? Will it be even solvable at this high limit? If yes, how, and if no, why?
3.I hope that this editorial somehow or the other, made you learn how to appreciate the small details provided by problem setters. I think most of us will agree on how the odd prime number made our life easy in this question!
