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.

1. if we have 2 factors, unique or not, the second person will always win.
2. if we have 3 factors, unique or not, the first person will always win.
3. if we have 4 factors, it depends.
   1. If all the factors are the same, the second person will win
   2. If one factor is different, however, either player can force a tie

By trying a few examples, we see that some player can force a tie if there is some prime factor of T that has an exponent LESS than the number of turns that the person has. For example, if the target is 2^3 * 3, The game will last at least 4 turns, and either player can force a tie by picking 3 twice.

We have one other quick fact. Note that a "winning" game for a given target T will always last the exact same number of moves, since each prime factor of T has to be picked exactly the number of times it appears in the prime factorization. Given this, for a given T, only one of two players can ever win. If the prime factorization has an even number of factors, the first person can never win. If it's odd, the second person can never win. So then it suffices to check if the "losing" party can force a tie.

1. number of factors = odd, check if second person can force a tie
2. number of factors = even, check if first person can force a tie
3. person can force tie if they have more turns than the minimum number of times some unique factor appears in the prime factorization

Run time is total time it takes to factor the number, which is sqrt(n)