### PROBLEM LINK:

**Author:** Vasya Antoniuk

**Testers:** Istvan Nagy

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

Simple

### PREREQUISITES:

finding pattern, game theory, understanding of winning and losing positions

### PROBLEM:

You have a pile containing n coins.

Two players play following game alternately. Each player in its turn can remove any prime power number of coins from the pile, i.e. p^x, s.t. p is a prime and x \geq 0. The player who can’t make his move loses the game. Find who wins the game.

### QUICK EXPLANATION:

Second player will win iff N \, \% \, 6 = 0, otherwise first player will win.

### EXPLANATION:

**Solution based on finding pattern**

We can find a pattern by writing a slow code to find the winner of the game for small numbers, say \leq 100. You can just implement the basic definition of winning/losing position in the game theory by writing a simple dp.

**More formal solution**

Let us try to see what happens for the game on some small examples.

For n = 1, first player will win.

For n = 2, 3, 5, first player will win as these numbers are prime.

For n = 4, the first player will also win as 4 = 2^2.

For n = 6, player can not remove 6 coins in his first turn, as 6 is not a prime power. Hence, whatever number of coins first player removes, he will end up with 1, 2, \dots, 5 coins, all of which are a wining positions for the other person. Hence, n = 6 is losing position for first player.

You can notice that numbers from n = 7 to 11, are also winning positions, as the first player can make a move such that remaining number of coins in the pile are equal to 6, which is a losing position.

For n = 12, the first player can win if he can move to some losing position, i.e. he could remove either 6 or 12 coins. He can’t remove any of these as they are not prime powers. So n = 12 is a losing position.

Similarly any multiple of 6 is a losing position, as you can’t make a move from n = 6 * k to any losing position, as you have to remove coins equal to some multiple of 6. A multiple of 6 can’t be a prime power, as 6 = 2 * 3.

### Time Complexity:

\mathcal{O}(1) - Just check whether N \, \% 6 \, = 0 or not.