Given a grid A of size N*M, 2 players are playing a game on it taking alternate turns. In each turn, a player chooses a subset of elements from any row and replaces each one of them with their proper divisor. A proper divisor of a number N is any divisor of N, not equal to N. The player who is unable to move, loses. Determine the winner of the game.
Problem Constraints:
1<=N, M<=10^3 1<=A[i][j]<=10^6
I suppose if you wanted the strategy of the loser, they would be able to play forever if there are at least 2 proper divisors of A[i][j]. Otherwise the other cases: (0, 1) and one are pretty simple to figure out. Can you please send the problem link, thanks.
Proper divisors of N are all divisors smaller than N.
Yes, but couldn't they just pick 1 and divide? As long as a[i][j] is greater than 1, they would be passing along their state to the other person, and vice versa. This would continue forever.
No, you replace those numbers with proper divisors, not divide them by that. If you divide N by 1 you get N and the problem doesnt allow that
If i had one nickle for every time i saw someone ask about this question in codeforces i would have two nickles, but it's kind of strange since it happened twice.
Here is my solution: https://mirror.codeforces.com/blog/entry/93095?#comment-819536