Submission #1574343

---

Source Code Expand

First consider an easier version of problem: we don’t divide the integers by their GCD. In
this case, obviously the answer only depends on the parity of the total number of stones. The
original problem also has something to do with parities.Suppose that in your turn all integers are odd. If all integers are one, you can’t perform any
operations and you lose. If not, you can perform an operation, and after the operation exactly
one integer is even and the others are odd (here the GCD doesn’t matter - since GCD is odd
in this case, it doesn’t change the parities). However, if your opponent perform an operation
on the only even number, you will again face the situation where all numbers are odd, and
you will lose eventually.If exactly one integer in your turn is even, you can always win. By performing an operation
in the only even number, you can force the opponent to lose (as described above).By similar observations, we get the following:1. In case there are odd number of even integers, you win. Your strategy is as follows. In
your turn you choose one of even numbers and perform an operation on it. After the
operation there will be two or more odd integers, so the GCD operation doesn’t change
the parities. Thus, in the opponent’s turn there will be even number of even integers,and in your next turn you will again have odd number of even integers. By repeating
this strategy, you always win.2. In case there are even number of even integers and two or more odd integers, you lose.No matter what you do, after your operation the opponent will be given a winning state,as described above.3. In case there are even number of even integers and exactly one odd integer. In this
case, it’s clear that if you perform an operation on one of even integers, you lose (your
opponent will face a winning state). Thus, you must perform an operation on the odd
integer, and after that divide all integers by their GCD. It’s not clear what happens in
this case - just simulate the game and solve the problem recursivelyWhen the simulation happens, all the integers are divided by at least two. Thus, the
number of simulations is O(log(max Ai)). The time complexity of the algorithm above is
O(N log(max Ai)

Submission Info

Compile Error

./Main.cpp:1:1: error: stray ‘\342’ in program
 First consider an easier version of problem: we don’t divide the integers by their GCD. In
 ^
./Main.cpp:1:1: error: stray ‘\200’ in program
./Main.cpp:1:1: error: stray ‘\231’ in program
./Main.cpp:3:1: error: stray ‘\342’ in program
 original problem also has something to do with parities.Suppose that in your turn all integers are odd. If all integers are one, you can’t perform any
 ^
./Main.cpp:3:1: error: stray ‘\200’ in program
./Main.cpp:3:1: error: stray ‘\231’ in program
./Main.cpp:5:1: error: stray ‘\342’ in program
 one integer is even and the others are odd (here the GCD doesn’t matter - since GCD is odd
 ^
./Main.cpp:5:1: error: stray ‘\200’ in program
./Main.cpp:5:1: error: stray ‘\231’ in program
./Main.cpp:6:1: error: stray ‘\342’ in program
 in this case, it doesn’t change the parities). However, if your opponent perform an operation
 ^
./Main.cpp:6:1: error: stray ‘\200’ in program
./Main.cpp:6:1: error: stray ‘\231’ in program
./Main.cpp:11:1: ...