This is my solution. The problem reduces to a simple nim game by the following argument...

For each tower: Let '' be the height of the tower. Let '' be the number of odd prime divisors of , e.g. for .

• If is odd, the size of the pile in the corresponding nim game is .
• If is even, the size of the pile is .

Reason why:

Each pair of towers of the same height can effectly be removed from the game because any move by a player on one of the towers can be copied by their opponent on the other tower. Therefore, breaking a tower into

• an even number of towers is effectively the same as removing it completely,
• an odd number is effectively the same as reducing it to a single smaller tower.

It follows that the highest power of that divides an even tower is irrelevant to chosing the optimal move, i.e. the factors are equivalent. Similarly all odd primes factors are equivalent. Thus an even tower of height is equivalent to a tower of height and the pile size in the corresponding nim game is , i.e. . Likewise an odd tower of height is equivalent to a tower of height and the pile size in the corresponding nim game is , i.e. .

Assuming you know very well about finding grandy value of every state . Now think about , a normal number 105 .

Its all divisors are

1, 3, 5, 7, 15, 21, 35, 105

So , Our tower with height(105) can be broken into 105/Z=35(Y) towers with all have equal size Z=3 . So grandy value of a state is the mex of all the possible states which can be reached by a valid move (mex is the minimum state that is not possible to be reached from that particular state ) .

Here , when we will break a tower (105) into 35(Y) towers with size of all 3(Z) .Then the grandy value of (105) will be G(105).

Where G(105) will be xor of all other grandy value of child towers of this father tower .

G(105) = G(3) ^ G(3)^G(3)^G(3)......... till 35(Y) times . But we can easily catch that if Y is odd then no need to xor of all Z . It will be obviously only G(3) as rest of all are even in number ( canceled out by the xor ) .

So , G(105)= G(3) when , we will break it into 35(Y) towers with size of all 3(Z) only and not take other possible state's grandy vale .

But we can break it into its all divisors according to question . More fromally ,we have to take into account all possible state's grandy value .So use sieve to calculate all divisors of a number till 100000 previously. Now according to question grandy of (105) will be mex of the set { G(1), G(3),G( 5), G(7), G(15), G(21), G(35),G( 105 ) } and another fact is when Y will be even for any Z ,then Xor will be zero i.e. G(Z) =0 . I hope all are clear . My pseudocode to find grandy recursively

 `int sg(int X)
{
    if(X==1)/// when the
    {
        return 0;
    }
    if(grandy[X]!=-1)/// if grandy value is already computed just return it , no need to calculate it
    {
        return grandy[X];
    }
    set<int>s;
    for(int i=0;i<divisors[X].size();i++)
    {
        int Y=divisors[X][i];/// the tower will be broken down into Y towers ,Y>1
        /// 1 is not included into any number's list of divisors during sieve ,so this Y will not be 1 never
        int Z=X/Y;/// Each of Y towers has height of Z , may be also height of 1 which will terminate our program by finding our grandy value of every X,as X=1 is base condition .
        if(Y%2==0) /// The number of towers are even then ,obviously its all tower's size will be canceled out as being of equal,grandy value will be 0 .
            s.insert(0);
        else  /// The number of towers are odd,obviously take only grandy value of one tower's size (Z).rest of the towers are canceled out by each other for xor technique.
            s.insert(sg(Z));
    }
    int mex=0;
    while(s.find(mex)!=s.end()) mex++;///checking which smallest number not included in the set.
    grandy[X]=mex;///assigning mex[not included minimum element in the set of grandy value of possible towers]
    return grandy[X];/// return grandy
}`

My full solution here :- https://github.com/joy-mollick/Game-Theory-Problems/blob/master/HackerRank-Tower%20Breakers%2C%20Again!.cpp

should

calculate prime factors except 2

#include <bits/stdc++.h>
using namespace std;
int OddPrime(int num)
    {
        int count = 0;
        if (num % 2 == 0)
            count++;
        while (num % 2 == 0)
        {
            num /= 2;
        }
        for (int i = 3; i <= sqrt(num); i++)
        {
            while (num % i == 0)
            {
                num /= i;
                if (i % 2 != 0) count++;
            }
        }
        if (num > 2)
            count++;
        return count;
    }
int main()
{
    int q;
    cin>>q;
    while(q--)
    {
        int n;
        cin>>n;
        int ans=0;
        int x;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            ans^=OddPrime(x);
        }
        if(ans!=0)
            cout<<1<<"\n";
        else
            cout<<2<<"\n";
    }
}

python 2 solution

def oddprimefactor(n):
    c = 0
    if n % 2 == 0:
        c += 1
    while n % 2 == 0:
        n /= 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            n /= i
            if i % 2 != 0:
                c += 1
        i += 1
    if n > 2:
        c += 1
    return c

for _ in range(int(raw_input())):
    n = int(raw_input())
    towers = map(int, raw_input().split())
    ans = map(oddprimefactor, towers)
    x = 0
    for i in ans:
        x ^= i
    print 2 if x == 0 else 1

Calculating grundy value using mex definition instead of an explicit formula works nicely as described in the editorial. But we can also reuse previous challenge result.

The grundy function g is the same as the one in previous challenge g'. All the divisors will be odd. By property of the nim sum, the grundy value for y towers of size z will be the same as for 1 tower of size z. So splitting tower x into y towers of size z is the same as replacing x by its divisor z.

g(x) = g'(x)

For y even, the nim sum cancels out and the next player loses. The grundy value is the same as well, but considering only primes other than 2 and offsetting by 1: Where alpha_2 is the exponent of prime factor 2,

g(x) = g'(x) - alpha_2 + 1

g' is the sum of the prime exponents in prime factorization. One could probably show this by induction on the number of prime factors and then on the prime exponent in the factorization. Same for above result.