#P1290. Euclid's Game
Euclid's Game
Euclid's Game
Two descendants of Euclid, Stan and Ollie, are playing a number game invented by their ancestor Euclid. Given two positive integers \(M\) and \(N\), the game is played as follows: starting with Stan, the player selects the larger of the two numbers and subtracts a positive integer multiple of the smaller number such that the result is non-negative. Then, the turn passes to the other player, who performs the same operation on the new pair (the most recent result and the other number). The game continues until a player obtains \(0\); that player wins.
For example, with the initial pair \((25, 7)\), the game might proceed as follows:
- Initial: \((25, 7)\)
- Stan: \((25 - 2 \times 7, 7) = (11, 7)\)
- Ollie: \((11, 7) \to (11, 7 - 1 \times 7) = (11, 4)\) (reordering gives \((4, 7)\))
- Stan: \((7 - 1 \times 4, 4) = (3, 4)\) (reordering gives \((4, 3)\))
- Ollie: \((4 - 1 \times 3, 3) = (1, 3)\)
- Stan: \((3 - 1 \times 1, 1) = (2, 1)\); note that with optimal play Stan eventually forces a win by reaching 0.
Assuming both players play optimally, determine which player will win the game. It is known that the winning strategy can be decided by simulating the game with the following rule: Let \(a\) and \(b\) be the two numbers with \(a \ge b\). If \(\lfloor a/b \rfloor \ge 2\) or \(a \mod b = 0\), then the current player wins immediately; otherwise, the outcome is the opposite of the result when playing with \(b\) and \(a-b\).
inputFormat
The input consists of a single line containing two positive integers \(M\) and \(N\) (\(1 \leq M, N \leq 10^9\)).
outputFormat
Output a single line: either Stan wins
if Stan (the first player) wins under optimal play, or Ollie wins
otherwise.
sample
25 7
Stan wins