Problem description:

以辗转相除法为基础,给定两个整数a和b,Stan和Ollie轮流从较大的数字中减去较小数字的倍数(整倍数),并且相减后的结果不能为零。Stan先手,在自己的回合将其中一个数变为零的一方获胜,当双方都采取最优策略时,谁会获胜?

a,b都是正整数。

Input:

a=34 b=12

Output:

Stan wins

找规律:

  首先,如果a>b则交换,假设a<b。另外,如果b已经是a的倍数则必胜,所以假设b不是a的倍数。此时a与b的状态有以下两种:

  (1) b-a<a  如果b减去a的2倍以及以上时会变为负数,所以b只能减去a。

  (2)b-a>a  有更高的倍数可以选择。

   对于(1)来说,因为没有选择的余地,如果b减去a之后所得到的状态是必败态的话,它就是必胜态。

  4.1.3 Euclid&#39;s Game (POJ 2348)-LMLPHP

  对于(2)来说,假设x是使得b-ax<a的整数,考虑b-a(x-1)的情况,对于(4,19)则减去12->(4,7)。

  此时,接下来的状态就变成了(1)没有选择的情况了。如果该状态是必败态的话,那么当前状态是必胜态。

  但是,如果b-a(x-1)后为必胜态,此时b-ax后的状态是b-a(x-1)后的状态唯一可以达到的状态,那么根据假设,如果b-a(x-1)后的状态是必胜态,所以该状态是必败态。

因此该状态是必胜态。

  由此可知,第二种情况总是必胜的。所以从初始状态开始,最先达到情况二的一方必胜。

//输入
int a,b;
void solve(){
bool f=true;
for(;;){
if(a>b) swap(a,b);
if(b%a==) break; //b是a的倍数时必胜
if(b-a>a) break; //如果是第二种情况必胜
b-=a;
f=!f;
}
if(f) cout<<"Stan wins";
else cout<<"Ollie wins";
}
05-11 13:37