題干：

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

題目大意：

? ?給出兩個數(shù)，a和b，將大的數(shù)中，減去若干b的倍數(shù)，最終有一個數(shù)為0的話就勝了。

解題報(bào)告：

貼bin巨博客：%bin巨

假設(shè)兩個數(shù)為a,b（a>=b)

如果a==b.那么肯定是先手獲勝。一步就可以減為0,b

如果a%b==0.就是a是b的倍數(shù)，那么也是先手獲勝。

如果a>=2*b. ?那么 那個人肯定知道a%b,b是必勝態(tài)還是必?cái)B(tài)。如果是必?cái)B(tài)，先手將a,b變成a%b,b,那么先手肯定贏。如果是必勝態(tài)，先手將a,b變成a%b+b,b.那么對手只有將這兩個數(shù)變成a%b,b,先手獲勝。

如果是b<a<2*b ?那么只有一條路：變成a-b,b ?(這個時候0<a-b<b).這樣一直下去看誰先面對上面的必勝狀態(tài)。

所以假如面對b < a <2*b的狀態(tài)，就先一步一步走下去。直到面對一個a%b==0 || a >=2*b的狀態(tài)。

AC代碼：

#include<bits/stdc++.h>using namespace std;int main() {int a,b;while(scanf("%d%d",&a,&b)) {if(a == 0 && b == 0)break;if(a < b) swap(a,b);int win = 0;while(b) {if(a%b == 0 || a/b >= 2) break;a = a-b;swap(a,b);win ^= 1;}if(win == 0) puts("Stan wins");else puts("Ollie wins");}return 0; }

總結(jié)：?

? ?找必?cái)↑c(diǎn)就好了。看題解總是感覺有道理，，，但是就是自己想不出來。。。難受難受

總結(jié)

以上是生活随笔為你收集整理的【 HDU - 1525 】Euclid's Game（较难找规律，玄学博弈，分析必败点必胜点）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。