题意过于简单,这里不在累赘。
思路
一个很经典的博弈论问题。
我们先考虑什么情况下先手必赢,首先最容易想到的就是 1,21,21,2 颗石子的情况,因为只需一步即可拿完。那么,先手必输的情况呢?333 颗石子的时候,先手无论怎么拿,最后一定会剩下 1,21,21,2 颗石子到后手时,一步即可拿完。
因为先手和后手是轮流交换的,所以只要先手操作后的石子数是先手必输局面,那么先手必赢(因为后手遇到了必输局面)。
同样的,如果先手无论如何操作都无法到达必输局面。那么先手是必输的(因为后手一定遇到了必赢局面)。依此类推。(可能有点难理解,可以自己尝试一下)
由于 nnn 颗石子下的结果是恒定的,于是我们可以输出从 111 到 nnn 颗石子的情况。
1 1 0 1 1 0 1 1 0 1 1 0...可以发现,无论 nnn 为多少,只要 3∣n3 \mid n3∣n 那么一定是比输局面,否则一定是必赢······