題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1525

Problem 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

題意：

兩個人，兩堆石頭，玩游戲。每次從石頭數多的那堆中拿走石頭數少的那堆石頭的個數的倍數個，保證拿了過后不能為負數。誰恰好使其中一堆石頭數為0，誰使其中某一堆石頭為0，誰贏。兩人都足夠聰明。

思路：

借助歐幾里得算法的博弈。

顯然如果a>b 且a>2*b ?先拿者必贏 因為他可以決定是自己還是對手遇到狀態（a%b,b）如果狀態（a%b,b）為必輸狀態，他就讓對手面對（拿走a-a%b個）。如果為必贏狀態，他就自己面對(拿走-a%b-b個).

如果b<a<=2*b 只能到達（a%b,b)的狀態。

#include<iostream> #include<cstdio> #define ll __int64using namespace std;int gcd(ll a,ll b) {if(a<b) //求出誰大swap(a,b);if(b==0) //終止 必輸狀態return 0;if(a>2*b) //必勝return 1;return gcd(b,a%b)^1; //和拿了之后的輸贏情況相反 }int main() {ll a,b;while(scanf("%I64d%I64d",&a,&b)!=EOF && a+b){int ans=gcd(a,b);if(ans)printf("Stan wins\n");elseprintf("Ollie wins\n");}return 0; }

總結

以上是生活随笔為你收集整理的HD 1525 Euclid's Game的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。