• 如果喜欢本站，您可以按CTRL+D收藏本站，方便下次访问。

• 欢迎来自五湖四海的朋友，期待为您分享有价值的资源

# POJ 2348-Euclid’s Game 博弈 取子

10年前 (2010-08-29) 219次浏览

Euclid\’s Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4525 Accepted: 1849 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

Waterloo local 2002.09.28

1,有一堆石子数目为一,先手必胜, 1,4, 1,2. 2,两堆石子数目差一,且两堆石子数目都不为一,先手必败(只能使后手面对必胜的局面),如 3,4 5,6 . 3,如果数目较大的那一堆是数目较小那一堆的2倍加减一,且不是上面两种局面,先手必胜,2,5 3,5 3,7.

1. N<2*M-1时,先手别无选择,只能使之变为 N-M,M 局面,(易见)如3,5 5,7 7,4…
2. 设两堆石子数目为N,M(N>M>0,且N,M互质),则若N>=2*M-1,且N – M ! =1时,先手必胜.要求M,N互质是因为对于M,N有公因数的情形,可以同时除以其公因数而不影响结果.

1. M,N先同时除以它们的最大公因数.(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;
}

====
• 版权声明

本站的文章和资源来自互联网或者站长的原创，按照 CC BY-NC-SA 4.0 CN协议发布和共享，转载或引用本站文章应保留来源网址，并遵循相同协议。如果有侵犯版权的资源请尽快联系站长，我们会在24H内删除有争议的资源。
• 网站驱动

• 友情链接

• 支持一下