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?

Submission