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之后所得到的状态是必败态的话,它就是必胜态。
对于(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";
}