题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1525
题目大意:Stan和Ollie在玩一个游戏,a和b两个数字,每次可以选择较大的数减去较小的数的若干倍,最后将大数减为0的人获胜。问给定的两个数字,谁会获胜。
后来的思路最后必然的局面是b,a%b,如果a>=b&&a<2*b,那么只有一种情况,直接到b,a%b。否则有多种情况。而a/b>=2的话,先手可以选择由谁面对b,a%b这样的局势,每一次的选择也可以决定后一次的抉择由谁进行选择,先手一直掌握先手优势,所以第一个获得先手优势的人必胜。
#include<stdio.h> #include<algorithm> using namespace std; int main() { int flag; int a, b; int c; int cnt; while(~scanf("%d%d",&a,&b)){ && b== ) break; if( a < b ) swap(a,b);//此时a>b flag = ; cnt = ;//cnt为偶数表示是S的操作回合 ){ && cnt % == ){ flag = ; break; } && cnt % == ){ flag = ; break; } c = a % b; a = b; b = c; cnt ++; // printf("%d %d \n",a,b); } == && flag == ) || flag == ) puts("Stan wins"); == && flag == ) || flag == ) puts("Ollie wins"); } }