这个题就是Bachet 游戏
结论:当且仅当 n≡0mod (m+1)n\equiv 0\mod(m+1)n≡0mod(m+1) 时先手必败,这个式子的意义是 nnn 除以 m+1m+1m+1 的余数是0。下面我们来准备证明一下,但我们的证明围绕了一个好东西:
如果一种游戏的最终局面(某一方输)满足某一性质,并且游戏中所有满足该性质的局面所能创造出的新局面都不满足该性质,同时所有不满足该性质的局面一定可以产生出至少一个满足该性质的局面,那么我们就可以根据最初局面是否满足这个性质来判断先手是否必胜。
证明:
首先发现最终局面是没有石子先手输了,显然此时满足结论。
当一个局面不符合时对应玩家可以取走这个余数数量的石子,显然数量上是合法的,后手会面临满足性质的局面
当一个局面满足性质的时候就一定不可能通过拿石子来得到,因为这样至少需要拿 m+1m+1m+1 个,不合法。
okk,证明结束,接下来就是代码了