787. Bézout's Game

Two players play a game with two piles of stones. They take alternating turns. If there are currently $a$$a$ stones in the first pile and $b$$b$ stones in the second, a turn consists of removing $c\ge 0$$c\geq 0$ stones from the first pile and $d\ge 0$$d\geq 0$ from the second in such a way that $ad-bc=\pm 1$$ad-bc=\pm1$. The winner is the player who first empties one of the piles.

Note that the game is only playable if the sizes of the two piles are coprime.

A game state $(a,b)$$(a, b)$ is a winning position if the next player can guarantee a win with optimal play. Define $H(N)$$H(N)$ to be the number of winning positions $(a,b)$$(a, b)$ with $gcd(a,b)=1$$\gcd(a,b)=1$, $a>0$$a > 0$, $b>0$$b > 0$ and $a+b\le N$$a+b \leq N$. Note the order matters, so for example $(2,1)$$(2,1)$ and $(1,2)$$(1,2)$ are distinct positions.

You are given $H(4)=5$$H(4)=5$ and $H(100)=2043$$H(100)=2043$.

Find $H({10}^9)$$H(10^9)$.

787. 裴蜀游戏

现有两名玩家用两堆石子玩一个游戏。二人轮流进行操作。
若某时刻第一堆里有 $a$$a$ 枚石子，第二堆里有 $b$$b$ 枚石子。则某名玩家在操作时，可以从第一堆里拿走 $c$$c$ 枚石子，从第二堆里拿走 $d$$d$ 枚石子，且满足：$c\ge 0$$c \geq 0$、$d\ge 0$$d \geq 0$、$ad-bc=\pm 1$$ad-bc=\pm1$。如果某玩家操作完毕后，取尽了某一堆石子，则该玩家获胜。

不难发现，只有当 $a,b$$a,b$ 互质时，这个游戏才能玩。

若某个状态 $(a,b)$$(a, b)$ 满足下一位玩家能在最优操作下保证获胜，则我们称这个状态为必胜态。再记 $H(N)$$H(N)$ 为满足 $gcd(a,b)=1$$\gcd(a,b)=1$、$a>0$$a > 0$、$b>0$$b > 0$ 且 $a+b\le N$$a+b \leq N$ 的必胜态 $(a,b)$$(a, b)$ 的个数。注意，本题考虑顺序问题。比如说，$(2,1)$$(2, 1)$ 和 $(1,2)$$(1, 2)$ 在计算时，应被认为是两个不同的状态。已知 $H(4)=5$$H(4)=5$、$H(100)=2043$$H(100)=2043$。

求 $H({10}^9)$$H(10^9)$。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。