Euclid's Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 893 Accepted Submission(s): 419
Problem Description
Two players, Stan and Ollie, play, starting with two natural numbers. Stan, the first player, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be nonnegative. Then Ollie, the second player, does the same with the two resulting numbers, then Stan, etc., alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0, and thereby wins. For example, the players may start with (25,7):
25 7
11 7
4 7
4 3
1 3
1 0
an Stan wins.
Input
The input consists of a number of lines. Each line contains two positive integers giving the starting two numbers of the game. Stan always starts.
Output
For each line of input, output one line saying either Stan wins or Ollie wins assuming that both of them play perfectly. The last line of input contains two zeroes and should not be processed.
Sample Input
34 12
15 24
0 0
Sample Output
Stan wins
Ollie wins
Source
University of Waterloo Local Contest 2002.09.28
Recommend
LL
題意：給你兩個數，每次可以拿大的那個數減去小的那個數的正整數倍，只要減去後得到的數是正的或者0就行，誰先得到其中一個數是0，誰就勝出。
我們會發現，假設a>b,如果a/b>=2,那麼後面就會出現a/b種路線，當a/b=1的時候只有一種路線，所以誰到了a/b>=2這個局面就有必勝策略，此外，當a%b==0的時候，就直接跳出來了，也是必勝點。
[cpp]
#include<iostream>
#include<cstdlib>
#include<stdio.h>
using namespace std;
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&(n&&m))
{
int count=1;
while(1)
{
if(n<m) swap(n,m);
if(n==0||m==0||(n/m>=2)||(n%m==0)) break;
n%=m;
count++;
}
if(count&1) puts("Stan wins");
else puts("Ollie wins");
}
}
