Multiplication Game

This problem presents a game where two players, starting at 1, take turns multiplying the current number by any factor of some target T, with the goal of landing on T exactly. The player that multiplies and ends on T is the winner. If the number ends up greater than T, it is a tie.

The classic solution to game theory problems is DP. Recurse over all possible moves, and see if there are any that allow me to force the other person to lose. The DP table stores for a given number, whether the player whose turn it is can force a win, a tie, or is guaranteed to lose.

1. for each factor
2. recurse on number * factor
3. if any recursion returns "lose," we can force a win (remember, once we recurse, it's the OTHER person's turn...so we want to leave them in a situation where they're guaranteed to lose
4. if any recursion returns "tie," we can at least force a tie
5. if all recursions return "win," the other player will always win, making forcing us to return "lose"

The DP table is 2^32 large, and we have 32 factors max...which makes our runtime 2^37....or way too big.

We can optimize this several ways.

First we can realize, if we ever are on a number which is NOT a factor of the target, the game must end in a tie. If our target is 10, and each person chooses 2, then we're at 4, with no way to ever hit 10 (so we'll go over). Turns out the number of total factors of a number is not very large, so our search space is much smaller. Second, we can realize that the amount of multiplications we have to make for each state is not 32, it is the number of UNIQUE prime factors of T. This number will be somewhere around 12. The first optimization SHOULD be enough.

We can do even better by thinking about the structure of the problem. First we note that a "won" game will always take exactly the same number of turns as the total number of factors in the prime factorization. This means only one person can possibly win the game (first player if odd number of factors, second player if even), and the other player will be trying to force a tie. We know exactly how many turns the "losing" player gets, and we know that in those turns, they have to choose some factor that has already been chosen enough times per the prime factorization (choosing 2 a second time in a game to 18, say). The first obvious criteria is if a person has more turns than the multiplicity of some prime factor, they can guarantee a win (in a game to 24, they can just choose 3 twice). This is not sufficient, however. Consider the example given of 30 (2*3*5). Only the first person can win, and the second player only gets 1 turn. So they can't force a tie? Well, obviously the CAN by just choosing the second number. We can show pretty easily that ANY number with 3 unique factors will result in a tie, because the minimum multiplicity cannot grow faster than n/3, but the number of turns in the game for a given player grows faster at n/2. This argument applies for all greater numbers of unique factors. So that leaves us with the following rules:

1. with 1 factor, someone will win. figure it out based on whether the multiplicity is even or odd
2. with 3 factors, the game will always end in a tie
3. with 2 factors, check whether the "losing" player has a number of turns greater than the minimum multiplicity of any prime factor

Factoring is sqrt(n), which is fast enough.