well, not so "Insipirational" of you, asking solution in here. lel ps- see their editorial o_O

$$$first$$$ $$$problem$$$ — if a player can choose any subset then the the most optimall way is too choose the whole row and replace it by it's divisor : $$$1$$$ then a player can't choose this row cos the divisors of $$$1$$$ are only $$$[1]$$$ and the statement says that : $$$A$$$ $$$proper$$$ $$$diviso$$$r $$$of$$$ $$$a$$$ $$$number$$$ $$$N$$$ $$$is$$$ $$$any$$$ $$$divisor$$$ $$$of$$$ $$$N,$$$ $$$not$$$ $$$equal$$$ $$$to$$$ $$$N.$$$ so we can't choose that row once again. Therefore we only need to check if the number of rows is odd : if it's , then player 1 win, otherwise player 2 win.

UPD : Oh what i wrote doesn't mean what i wanted to say... — $$$Replace$$$ $$$every$$$ $$$row$$$ $$$with$$$ $$$number$$$ $$$1$$$ $$$(which$$$ $$$is$$$ $$$a$$$ $$$divisor$$$ $$$of$$$ $$$any$$$ $$$number)$$$ $$$and$$$ $$$then$$$ $$$a$$$ $$$player$$$ $$$which's$$$ $$$turn$$$ $$$can't$$$ $$$choose$$$ $$$that$$$ $$$row$$$.

lol codenation

Here is my solution to problem 1: We can do two reductions to make this problem become a game of NIM (see more in here, but i'll explain it later).

• Let's define f(n) the maximum number of times you can do the operation of replacing n with a proper divisor of it. For the number 24 for example, which is 2^3*3^1, f(24) = 4. Notice that we can change 24 to a number x such that f(x) can be either 3 (8 for example), 2 (4 for example), 1 (2 for example) and 0 (that number would be 1). As this tells us more about the problem than the number in question than the actual number, let's use f(A[i][j]) instead of A[i][j] (we can find it using the sieve of erastothenes in O(10^6*log(10^6)) + N*M).

• Since we can use any subset on a row, let's use the same idea again. We define g(A[i]) the maximum number of operations we can do in a row, and from a g(A[i]) we can reduce it to a g(x) such that g(x) can be equal to any integer from 0 to g(A[i]) — 1.

This is exactly NIM. We have many piles of rocks (in this cases, the piles are the rows and the ammount of rocks are the g(A[i])) that we can take any non zero ammount of rocks out of and the loser is the one that can't do any moves anymore. For a game of nim, if someone starts the game in such a way that the bitwise XOR of all piles is 0, they lose. Otherwise, they win. You can read about the proof here, but the idea is that from a state where the bitwise XOR is different from 0, you can make the bitwise XOR 0, but from XOR = 0 you can only make XOR different from 0, and since the losing state has bitwise XOR = 0, then we can keep taking rocks out in a way that guarantees a win.

Take the bitwise xor of all g(A[i]) and print 1 or 2 accordingly.

does not work

The first question is a direct application of Nims Theorem. Consider each row as a pile of stones and the number of stones in that pile is equal to the sum of number of times you can replace each number of that row with a proper divisor.

The second question is same as 734E - Anton and Tree

[redacted]

Please provide these types of questions more.