POJ2348 Euclid's Game

题目地址

题解

假设$a>b$。
显然当$a\mod b=0$时,先手必胜。
当$a\mod b\neq 0$时,若$a>2b$,则可以证明在接下来先手所有可以采取的$k$种策略中必有必胜策略,故这个也是必胜态。
我讲的比较浅显,各位不妨看下《挑战程序设计竞赛》的P310。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long ll;
ll a,b,f;
int main(){
for(;;){
scanf("%lld%lld",&a,&b);
if(!a&&!b)break;
f=1;
for(;;){
if(a<b)swap(a,b);
if(a%b==0)break;
if(a>2*b)break;
a-=b,f^=1;
}
if(f)printf("Stan wins\n");
else printf("Ollie wins\n");
}
return 0;
}