Problem, Editorial

Given n numbers a[1] to a[n], 2 player play a game alternately as follows. In the beginning of game, we have a number g = 0. They chose one of the numbers in the array a which is not thrown out and replace g by gcd(g, a[i]). After that they throw a[i]. If at any time in the game g becomes 1, the person who made the value g of equal to 1 loses. If a person is not able to move, then also he loses.

There are two questions to answer. 1. Who will win if they play optimally. 2. What is probability of winning of first player if they play randomly.

I'd like to share my solution to part 2 which is different from the editorial.

Any game they play is a permutation of a (let them play all n numbers, even someone already lose). Let's call this permutation b. Since they play uniformly randomly, the permutation is also chosen uniformly randomly from all n! permutations.

Let for 1 ≤ k ≤ n.

If the game ends exactly on the k th turn, that means , but . Therefore the probability is prob(k - 1) - prob(k). If prob(n + 1) is defined as 0, then k = n + 1 is also applied. Sereja wins if and only if the game ends on even number turns, so the answer is (prob(1) - prob(2)) + (prob(3) - prob(4)) + ....

All that's left is calculate prob(k). Let , we can calculate separately the probability that g_k is a multiple of p, where p is a prime, and add them up. By the inclusion-exclusion principle, we also have to subtract the probability that g_k is a multiple of p₁ p₂, where p₁ and p₂ are primes, and add back the probability that g_k is a multiple of p₁ p₂ p₃, where p₁, p₂ and p₃ are primes. Fortunately, there is no number under 100 having 4 different prime factors.

Finally, let's calculate the probability that g_k is a multiple of m. Say there are c numbers in a that are multiples of m. Note that b₁, b₂, ..., b_k must all be multiples of m, so all chosen from these c numbers. The number of combinations is and the number of permutations is . So the probability is .

My solution: http://www.codechef.com/viewsolution/3906540