2
$\begingroup$

Let some finite array of integers is given initially.

There is a number k which is initially '0'.

In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]).

Also, the number chosen from the array(i.e a[i]) will be removed from that array.

CONSTRAINTS

A player who makes k=1 at any step loses. A player who cannot move also loses. 2 players are playing the game optimally.

When will the player who moves first wins the game?

$\endgroup$
  • $\begingroup$ this seems related to the Sylver Coinage game: en.wikipedia.org/wiki/Sylver_coinage $\endgroup$ – mobius dumpling May 6 '14 at 12:56
  • $\begingroup$ @mobiusdumpling I have seen that game before,But how can we reduce it to this one. $\endgroup$ – user2573642 May 6 '14 at 16:57
  • 3
    $\begingroup$ This seems to be identical to the problem codechef.com/MAY14/problems/SEAGM, which is a problem on a currently ongoing contest. It's probably best to at least wait until the contest is over before answering. $\endgroup$ – jschnei May 6 '14 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.