### PROBLEM LINK:

**Author:** Konstantin Sokol

**Tester:** Gerald Agapov

**Editorialist:** Tasnim Imran Sunny

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Game Theory, Sieve of Erasthosenes

### PROBLEM:

Two players are playing a game where they start with an integer **N**. At each move a player can decrease the integer by 1 or divide it by one of it’s divisor except itself and 1. The players have turns to give one move alternately. The player who cannot make any move ( the integer becomes 1) loses the game. Determine who would win the game if they start with **N**.

### EXPLANATION:

If you are not familiar with “Game theory” problems, read this tutorial before.

The terminal position ( here it is **N=1**) is a losing position. A position is winning if it is possible to move to a losing position in one move. And a player is in a losing position if he can move to winning positions only.

The simplest way to solve this problem would be to notice the pattern by analyzing all the winning/losing positions between 2 and M (where M is a reasonable value say 10000) with a straightforward DP solution. The pattern is that all prime numbers except 2 and 17 are losing positions. All composite numbers except 16, 34 and 289 are winning positions. So the solution is just to check whether the number is a prime or a composite number.

**Proof:**

Here are the positions for **N** up to 15.

```
N = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
position[] = L W L W L W L W W W L W L W W
```

**When N = 2 ^{n} where n >= 1:**

**N**= 2, 4 and 8 are winning because 1,3 and 7 are losing positions. But 16 is not winning since {2,4,8,15} are not losing positions. But for all other powers of 2 greater than 16, the player can make a move to 16 and thus winning, so all the other powers of 2 are winning.

**When N = 17 ^{k} where k >= 1:**

**N**= 17 is winning since 16 is losing position.

**N**= 17

^{2}= 289 is losing since {17, 288} are winning positions.

For all other greater powers of 17, the player can make a move to losing position 289 and thus winning the game, so all other powers of 17 are winning.

***When N = 2 ^{n} 17^{k} where n >= 1 and k >= 1:**

The smallest such

**N**= 34 is losing, since {2, 17, 33} are all winning positions.

But for any other multiples of 34, the player can make a move to losing position 34 and thus winning, so any other multiple of 34 would be winning.

**When N = Number having at least one prime divisor which is not 2 or 17:**

It can be proven that all such prime numbers are losing positions and all such composite numbers are winning. Consider an algorithm similar to Sieve of Erasthoneses:

- Find the smallest number
**N**which is not determined yet whether winning or losing - Determine the state of that position
- If it is losing then mark all it’s multiples as winning positions.Because then all multiples of
**N**would have a losing divisor**N**, so those would be winning.

Let’s start with the first number 3 which is losing position (since 2 is winning), so all the multiples of 3 would be winning. The next undetermined number would be the next prime number 5 and that would be losing too and all it’s multiples would be winning. The next undetermined position would always be a prime number( without considering 17) **P** and that would be losing since the composite number **P-1** would be marked losing by one of it’s losing prime divisor. All composite numbers having prime factor other than 2 or 17, would always be winning since it would be marked winning by one of it’s losing prime divisor.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.