NOI 4.2 數論 1350:Euclid's Game

題目來源：http://noi.openjudge.cn/ch0402/1350/

1350: Euclid's Game

總時間限制 : 1000ms  記憶體限制 : 65536kB

描述

Two players, Stan and Ollie, play, starting with two naturalnumbers. Stan, the first player, subtracts any positive multiple of the lesserof the two numbers from the greater of the two numbers, provided that theresulting number must be nonnegative. Then Ollie, the second player, does thesame with the two resulting numbers, then Stan, etc., alternately, until oneplayer is able to subtract a multiple of the lesser number from the greater toreach 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 twopositive integers giving the starting two numbers of the game. Stan always starts.

輸出

For each line of input, output one line saying either Stan winsor Ollie wins assuming that both of them play perfectly. The last line of inputcontains two zeroes and should not be processed.

樣例輸入

34 12
15 24
0 0      

樣例輸出

Stan wins
Ollie wins      

來源

Waterloo local 2002.09.28

-----------------------------------------------------

思路

【題意】

Stan和Ollie用兩個整數a,b做遊戲，Stan先手。兩人輪流把兩個數中較大者減去較小者的一個正整數倍，且使得結果仍是非負數。如此進行下去，直到某人操作過後出現一個0，則該人獲勝。現給出a,b，問誰有必勝政策。

【思路】

不妨設每輪中a是較大者。對每輪操作，都可以分3種情況讨論：

1. a % b == 0, 先手必勝

2. a > 2*b, 此時先手至少有(a%b, b)和(a%b+b, b)兩種操作的選擇。注意到(a%b+b, b)再經過一次操作可以得到(a%b, b)，故(a%b, b)和(a%b+b, b)分别對應兩個人的必勝情況。此時先手可以從中選一個屬于自己的必勝情況，是以一旦出現a > 2*b，先手必勝

3. b < a < 2*b, 此時先手隻有一種選擇: (a-b, b). 對(a-b, b)重複該讨論

故出現情況1和情況2時可以直接判斷是先手勝，出現情況3則循環直到出現情況1或情況2再判斷。

【坑點】

一定要long long！ 不用long long 用int隻有5分！ZOJ上也是這樣，隻有HDU上用int可以AC.

-----------------------------------------------------

代碼

#include<iostream>
using namespace std;

void swap (long long &a, long long &b)					// 把a變為ab較大者，b變為ab較小者
{
	int aa,bb;
	aa = max(a,b);
	bb = min(a,b);
	a = aa;
	b = bb;
}


int main()
{
	long long a,b;
	bool flag;
	while (cin >> a >> b)
	{
		if (a==0 && b==0)
		{
			break;
		}
		flag = true;
		swap(a,b);
		if (a%b==0)
		{
			cout << "Stan wins" << endl;
			continue;
		}
		while (a>b && a<2*b)
		{
			a = a-b;
			swap(a,b);
			flag = !flag;
		}
		if (flag)
		{
			cout << "Stan wins" << endl;
		}
		else
		{
			cout << "Ollie wins" << endl;
		}
	}
	return 0;
}