Editorial for recently ended NPL qualifier:- https://www.codechef.com/NPLQ2017/problems/NPL1701C
and https://www.codechef.com/NPLQ2017/problems/NPL1701F ??
EDIT- @vijju123 here - If editorials not possible, provide him with some quick explanation or something such that he gets going. Thanks!
regarding https://www.codechef.com/NPLQ2017/problems/NPL1701C
i have solved this but not sure whether i am fully correct or not as the problem is not still available in practice section.
my approach : first notice that it the number of factors that the number(A[i]) has matters not the number itself! Suppose a number has 3 factors then Appu has the only choices : i) to break this into (1, 2) i.e a number with one factor and the other with two factors, now you can see the first number cannot be broken further. So, the second number decides the winner. Now the second player has only one choice i.e. to break this into numbers that have only one factors and that’s the end of the game. So, as we can see that whatever the number is if it has three factors then second player will won.
Now, we can find the winner if there is only a single number on which the game depends (above cases 3 or 2 that has no other moves). If, there are multiple states i.e. (3, 2 , 1, 5) (numbers with 5 factors, 2 factors, 1 factor, and 3 factors) and if we know the answer of every single state then we can use sprague grundy theorem to calculate the answer of current state( which states that the answer is the XOR of all the states) !
Lets take an example :
suppose we have to find our answer for a number with 5 factors(suppose we have the answer of all the previous states i.e. 1 to 4) : the possible states which the first player can broke into it --> (1, 4), (2, 3) .
Now, for state (1, 4) the answer will be (state[1] ^ state[4]) and similarly for (2, 3) --> (state[2]^state[3]), now we have all these values so, we can easily get the answer of these two states and we now see that if any of these states will lead to win or not ! if yes then simply the answer of state[5] is yes otherwise it will be zero (losing state).
finally after getting the all the states possible (here you can see at max 20 states are possible as 2^20 ~ 10^6). so, calculate those in a brute approach and then just xor all the states to get the answer of the queries !
my code : https://ideone.com/LFGknR
if you have doubts feel free to ask 