# Grundy Number

I have been trying to solve the above problem. It is clear to me that above question is to be solved by sprague-grundy theorum, but since I am new to the topic I am not able to break it into independent games and there is also no Editorial available for the given problem.

Thanks for Help!

Assume there are A_i objects at each index. You have to treat each object seperately. You can calculate the grundy numbers with a simple dp. Let G_i denote the grundy number at i, and the grundy number of a wrong index is infinity.

It’s just G_i=MEX(G_{2i}, G_{3i}, G_{5i}). Now since there can be 10^9 objects at each index, the xor of all the objects at an index is G_i if they are odd, and 0 if they are even.

https://www.codechef.com/viewsolution/33436028

2 Likes

@everule1 Thanks, I got it.
Basically unlike normal cases of sprague-grundy, here we considered the states where one single element of any index can transit. So for any index , its grundy number will be xor of grundy numbers of all its elements which is g if X[i] is odd, and 0 if it is even.

Wonderful approach!