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.
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.
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.
Waterloo local 2002.09.28
給定兩堆石子,二人輪流取子,要求只能從石子數(shù)目較大的那一堆取子,取子的數(shù)目只能是另一堆石子數(shù)目的倍數(shù).最終使得某一堆數(shù)目為零的一方為勝.
首先,容易看出,對于每一個局面,要么是先手必勝,要么是后手必勝,最終結(jié)果完全由當(dāng)前局面完全確定.
另外,可以簡單羅列一下先手必勝和必敗的幾種局面(兩堆石子初始數(shù)目都大于零):
1,有一堆石子數(shù)目為一,先手必勝,? 1,4,??? 1,2.
2,兩堆石子數(shù)目差一,且兩堆石子數(shù)目都不為一,先手必敗(只能使后手面對必勝的局面),如? 3,4? 5,6?? .
3,如果數(shù)目較大的那一堆是數(shù)目較小那一堆的2倍加減一,且不是上面兩種局面,先手必勝,2,5? 3,5? 3,7.
可是上面這些信息對于解決這個問題還是有一些困難.
再進一步試算數(shù)目較小的石子,可以發(fā)現(xiàn),當(dāng)兩堆數(shù)目相差較大時,總是先手必勝.
事實上,進一步探討可以發(fā)現(xiàn)下面的結(jié)論:
1,N<2*M-1時,先手別無選擇,只能使之變?yōu)?N-M,M 局面,(易見)如3,5? 5,7? 7,4...
2,設(shè)兩堆石子數(shù)目為N,M(N>M>0,且N,M互質(zhì)),則若N>=2*M-1,且N - M ! =1時,先手必勝.要求M,N互質(zhì)是因為對于M,N有公因數(shù)的情形,可以同時除以其公因數(shù)而不影響結(jié)果.
簡單說明一下上面結(jié)論2的由來. N>=2*M-1時,先手可使之變?yōu)? N%M,M? 或N%M+M,M兩種局面之一,其中有且只有一個必敗局面。注意到如果N%M,M不是必敗局面，那么N%M+M,M就是必敗局面，因為面對N%M+M,M這個局面，你別無選擇，只能在前一堆中取M個使對方面對必勝局面(結(jié)論1 )。
據(jù)此可設(shè)計算法如下:
1.M,N先同時除以它們的最大公因數(shù).(M<N)
2,如果M==0,則返回零;
3,如果M==1,則返回一;
4,如果N>=M*2-1,則返回一
5,令N=M,M=N-M,遞歸處理
#include?<iostream>
using?namespace?std;
long?long?gcd(long?long?a,long?long?b)
{
????if(a==0)
????????return?b;
????return?gcd(b%a,a);
}
long?long?Eu(long?long?m,long?long?n)
{
????if(m==1)
????????return?1;
????if(n-m==1?&&?m)
????????return?0;
????if(n>=m*2-1)
????????return?1;
????return?!Eu(n%m,m);
}
int??main()
{
????long?long?m,n,temp;
????while?(cin>>m>>n?&&?(m||n))
????{
????????long?long?g=gcd(m,n);
????????m/=g;
????????n/=g;
????????if(m>n)
????????{
????????????temp=m;
????????????m=n;
????????????n=temp;
????????}
????????if(Eu(m,n))
????????????cout<<"Stan?wins"<<endl;
????????else
????????????cout<<"Ollie?wins"<<endl;
????}
????
????return?0;
}