Am i missing some test case, because it’s very clear from the question itself that we have to remove all the element those who share common smallest prime factor and the one who can’t make move win’s
Facorization game problem
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.
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.