The Divisor Game — Solution & Editorial
Induction shows even N wins and odd N loses: every divisor of an odd number is odd, so odd always hands the opponent even; from even you can always subtract 1.
Complexity: O(1)
Induction shows even N wins and odd N loses: every divisor of an odd number is odd, so odd always hands the opponent even; from even you can always subtract 1.
Complexity: O(1)