← 完整题目索引

PROJECT EULER · #0665

比例尼姆游戏

Proportionate Nim

仅题目 · 待解原题 ↗

两名玩家轮流玩两堆石子的游戏。

在每一回合,相应的玩家选择一个正整数 n 并执行以下操作之一:

  • 从一堆石头中取出 n 个石头;
  • 从两堆石头中取出n个石头;或
  • 从一堆中移除 n 石子,从另一堆中移除 2n 石子。

移走最后一块石头的玩家获胜。

我们用 (n,m) 表示堆中剩余 n 和 m 石子的位置。请注意,(n,m) 被认为与 (m,n) 位置相同。

那么,例如,如果位置是(2,6),则下一个玩家可能到达以下位置:
(0,2)、(0,4)、(0,5)、(0,6)、(1,2)、(1,4)、(1,5)、(1,6)、(2,2)、(2,3)、(2,4)、(2,5)

如果接下来移动的玩家无法强制获胜,则该位置为失败位置。例如(1,3)、(2,6)、(4,5)是前几个亏损的仓位。

令 f(M) 为所有亏损仓位 (n,m) 的 n+m 之和,其中 n≤m 和 n+m≤M。例如,f(10)=21,考虑亏损仓位 (1,3)、(2,6)、(4,5)。

已知 f(100)=1164 且 f(1000)=117002。

找到f(107)。

题解待补充

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