### PROLEM NAME:

ENDGAME

### PROBLEM LINK:

### 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 = 2n 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 = 17k where k >= 1:**

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

**N** = 172 = 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 = 2n 17k 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.

### SOLUTION:

```
#include <iostream>
#include <cstdio>
#define mp make_pair
#define pb push_back
using namespace std;
bool fun( int n )
{
if ( n == 2 ) return true;
if ( n == 16 ) return false;
if ( n == 17 ) return true;
if ( n == 34 ) return false;
if ( n == 289 ) return false;
for ( int i = 2; i * i <= n; i++ )
if ( n % i == 0 )
return true;
return false;
}
int main (int argc, const char * argv[])
{
int test; scanf("%d", &test);
while ( test-- )
{
int n;
scanf("%d", &n);
if ( fun( n ) ) puts("Steve"); else puts("Tony");
}
return 0;
} ```
```