Please can you tell me how to approach this question

#1

please can you tell me how to approach this question

#2

In which language would like to be explained the solution? C++/Java
Or do you prefer the algorithm first and will like to implement on your own?

#3

algorithm first i will try implementing on my own

#4

2
4
1 2 3 5
4
3 18 2 2

In the first move,player1 chooses one prime from the set {2, 3, 5}. If he chooses 2, then he has to choose the subset containing only the value 2 from the array and divide it by 2. In the next move, player2 chooses one of the primes {3, 5}. If he chooses 3, then he has to choose the subset containing only the value 3 from the array and divide it by 3. In the last move, player1 repeats the same with the prime 5. player2 now cannot make a move and he loses.

#5

The general algorithm applied is as follows:-
Consider the simple case, if all numbers consist only of powers of a particular prime p . At any instance we can choose any non-empty subset of these numbers and divide each of them by any power of p . This can be considered as just one number which is product of all given number, which will make it of the form p^a. Also, we can reduce its power(a) to any number of our choice. It’s quite evident that game has winning position when a is not equal to 0
Hence, If all numbers are powers of p, then we are in winning position only if total of power of p across all numbers is non-zero.

Game is independent for each distinct prime p. We can consider grundy number of each independent game as total power of a prime across all given numbers, and resultant grundy number of the game will be xor of all these grundy numbers across independent games

Find all primes by Sieve of Eratosthenes till maximum given number, and check power of each prime in each given number.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.