Euclid's Game
| Time Limit: 1000MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
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):
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
博弈题（有难度）
题意：
给你两个数m和n。然后两个人分别对这两个数进行如下操作：
1.只能对大的数操作，即大数减小数的倍数（1...k）更新这个数。
2.谁的操作是两个数中一个变为0便获胜。
分析：
说实话到现在还是有点迷糊；特别是到最后时很难弄清状态；
这里有网上的报告：
http://www.cppblog.com/sdz/archive/2010/08/29/125124.html
Code
| Problem: P | User: sdau_09_zys | |
| Memory: 240 KB | Time: 0 MS | |
| Language: C++ | Result: Accepted | |
| Public: | ||
#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; }