← 完整题目索引

PROJECT EULER · #0325

石子游戏 II

Stone Game II

仅题目 · 已解决原题 ↗

游戏由两堆石子和两名玩家进行。
在每个玩家的回合中,玩家可以从较大的一堆石头中移除一些石头。
移除的石子数量必须是较小堆中石子数量的正倍数。

例如让有序对 (6,14) 描述一个配置,其中较小的一堆中有 6 石子,较大的一堆中有 14 石子,那么第一个玩家可以从较大的一堆中取出 612 石子。

从一堆石头中取出所有石头的玩家赢得游戏。

获胜配置是第一个玩家可以强制获胜的配置。例如,(1,5)(2,6)(3,12) 是获胜配置,因为第一个玩家可以立即移除第二堆中的所有石子。

失败配置是指无论第一个玩家做什么,第二个玩家都可以强制获胜。例如,(2,3)(3,4) 正在丢失配置:任何合法的移动都会为第二个玩家留下获胜配置。

S(N) 定义为所有丢失配置 (xi,yi),0<xi<yiN(xi+yi) 之和。
我们可以验证S(10)=211S(104)=230312207313

查找 S(1016)mod710

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。