While solving Problem C of the recent contest, my thoughts were-
If $$$n$$$ is $$$1$$$, then Ashishgup cannot make any move and therefore he loses.
If $$$n$$$ = $$$2$$$, In the first turn Ashishgup will decrement the number providing $$$1$$$ to the opponent and thereby winning.
If $$$n$$$ is Odd, Ashishgup can always divide by the number itself and provide $$$1$$$ to the opponent, thereby winning
Otherwise, I tried to visualise the problem as prime factorization.
The Prime Factorization of any number can be of the form: $$$ 2^3 * 3^3 * 17^1 ...$$$ etc, where two is the only prime factor and rest are all odd as every prime no apart from $$$2$$$ is odd. Therefore, the factorization can be rewritten as $$$ evenPart * OddPart$$$ where the $$$evenPart$$$ consists of some power of $$$2$$$ and $$$oddPart$$$ is the full product of the rest of the prime numbers.
Ran a loop till $$$ \sqrt{n} $$$ and for every factor, I check if $$$n/OddFactor$$$ is even. The idea being that if we provide a number with no odd factors to FastestFinger on the next turn, Ashishgup will win.
The only caveat is that if $$$n/OddFactor$$$ is $$$2$$$ , then AshishGup loses.
Is my train of thought right?
