← 完整题目索引

PROJECT EULER · #0787

贝祖的游戏

Bézout's Game

仅题目 · 待解原题 ↗

两个玩家玩两堆石头的游戏。他们轮流轮流。如果当前第一堆中有 a 石头,第二堆中有 b 石头,则一轮包括从第一堆中移除 c≥0 石头并从第二堆中移除 d≥0,方式为 ad−bc=±1。第一个清空其中一堆的玩家获胜。

请注意,只有当两堆大小互质时,该游戏才可以玩。

如果下一个玩家能够以最佳发挥保证获胜,则游戏状态 (a,b) 就是获胜位置。定义 H(N) 为获胜位置 (a,b) 的数量,其中 gcd(a,b)=1,a>0,b>0 和 a+b≤N。请注意顺序很重要,例如 (2,1) 和 (1,2) 是不同的位置。

您获得 H(4)=5 和 H(100)=2043。

求H(109)。

题解待补充

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