Project Euler 787

发表于 分类于 阅读次数： 本文字数： 4.2k 阅读时长 ≈ 4 分钟

Project Euler 787

题目

Bézout’s Game

Two players play a game with two piles of stones. They take alternating turns. If there are currently \(a\) stones in the first pile and \(b\) stones in the second, a turn consists of removing \(c\geq 0\) stones from the first pile and \(d\geq 0\) from the second in such a way that \(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)\) is a winning position if the next player can guarantee a win with optimal play. Define \(H(N)\) to be the number of winning positions \((a, b)\) with \(\gcd(a,b)=1\), \(a > 0\), \(b > 0\) and \(a+b \leq N\). Note the order matters, so for example \((2,1)\) and \((1,2)\) are distinct positions.

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

Find \(H(10^9)\).

解决方案

假设当前 \((a,b)\) 互素，且做了一步合法操作得到 \((a',b')=(a-c,b-d)\)。注意到：\((a-c)d-(b-d)c = ad-bc=\pm1.\)

因此任何同时整除 \(a-c\) 与 \(b-d\) 的公因子也必须整除 \(\pm1\)，只能是 \(1\)。\(\gcd(a',b')=\gcd(a-c,b-d)=1.\)

所以从互素状态出发，走到的下一个状态仍然互素，游戏一直可继续直到终止。

下面固定 \(a<b\) 且 \(\gcd(a,b)=1\)。考虑方程\(ad-bc=1.\)模 \(b\) 意义下，有\(ad\equiv 1\pmod b.\)

因为 \(\gcd(a,b)=1\)，\(a\) 在模 \(b\) 下可逆，所以存在唯一的 \(d\)（在 \(1\le d\le b-1\) 范围内）满足该同余。于是\(c=\dfrac{ad-1}{b}\)是一个非负整数，并且由于 \(d<b\)，有 \(ad<ab\)，从而 \(c\le a-1\)，合法。

同理，对\(ad-bc=-1\)等价于\(ad\equiv -1\pmod b,\)也会得到唯一的一组合法解。

更强的是：这两组解具有互补关系。设 \((c_+,d_+)\) 满足 \(ad_+-bc_+=1\)，令\(d_- = b-d_+, c_- = a-c_+.\)则直接计算：\(ad_- - bc_- = a(b-d_+) - b(a-c_+) = -(ad_+-bc_+)=-1.\)

因此两步操作分别对应：

  • \((+1)\)：移走 \((c_+,d_+)\)
  • \((-1)\)：移走 \((c_-,d_-)=(a-c_+,, b-d_+)\)

并且它们满足\(c_+ + c_- = a, d_+ + d_- = b.\)

不失一般性，假设 \(a<b\)。对任意合法一步，令 \((a',b')=(a-c,b-d)\)。由前面的推导可写成（分别对应 \(\pm1\)）：\(a'=\dfrac{a(b-d)\pm 1}{b}, b'=b-d.\)比较 \(a'\) 与 \(b'\)：

  • 对 \(+1\) 情况：\(a'\le b' \iff a(b-d)+1 \le b(b-d)\iff (b-d)(b-a)\ge 1.\)因为 \(b-d\ge 1\) 且 \(b-a\ge 1\)，成立（极端等号只会出现于一步走到 \((1,1)\)）。
  • 对 \(-1\) 情况更显然严格小于：\(a' < b'.\)因此，从区域 \(a<b\) 出发，下一步仍落在 \(a'\le b'\) 的区域内。

这点非常关键，这说明我们可以只研究 \(a<b\) 的半平面结构。

通过以下程序打表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50;
bool ok[N+4][N+4];
int main(){
    int ans=0;
    for(int a=1;a<=N;a++)
        for(int b=a;b<=N;b++){
            if(__gcd(a,b)!=1) continue;
            if(a>b) ok[a][b]=ok[b][a];
            else{
                for(int c=0;c<=a&&!ok[a][b];c++){
                    if((b*c+1)%a==0){
                        int d=(b*c+1)/a;
                        if(d<=b&&!ok[a-c][b-d]) ok[a][b]=1;
                    }
                    if((b*c-1)%a==0){
                        int d=(b*c-1)/a;
                        if(d<=b&&!ok[a-c][b-d]) ok[a][b]=1;
                    }
                }
            }
            if(ok[a][b]) ++ans,printf("%d %d\n",a,b);
        }
    printf("%d\n",ans);
}

在 \(a<b\) 且 \(\gcd(a,b)=1\) 的前提下，我们可以看到：\((a,b)\)是必胜局面，当且仅当\(a\)是奇数。 我们接下来使用数学归纳法来证明这个结论。

  • 归纳基础：\((1,2)\) 可以一步走到清空一堆（直接赢）；而 \((2,3)\) 可验证为先手必败。小规模完全成立。
  • 归纳假设：对所有 \(a'+b' < a+b\) 的互素状态 \((a',b')\)（并且 \(a'<b'\)），结论成立。

若 \(a\) 为偶数，则当前为必败。 因为 \(\gcd(a,b)=1\) 且 \(a\) 偶数，所以 \(b\) 必为奇数。对任意合法操作满足 \(ad-bc=\pm1\)，模 \(2\) 下，有：\(ad-bc \equiv 0\cdot d - 1\cdot c \equiv -c \equiv 1 \pmod 2,\)

因此 \(c\) 必为奇数，于是\(a' = a-c \equiv 0-1\equiv 1\pmod 2,\)即新状态的第一项 \(a'\) 一定是奇数。再结合上一节的单调性仍有 \(a'<b'\)，所以根据归纳假设，新状态是必胜局面。也就是说，从 \(a\) 偶数的局面出发，所有合法走法都会把对手送进必胜局面，因此当前局面必败。

若 \(a\) 为奇数，则当前为必胜。 此时仍有且仅有两种走法，它们对应的移除量满足\(c_+ + c_- = a.\)因为 \(a\) 是奇数，所以 \(c_+\) 与 \(c_-\) 一奇一偶。选择那个 \(c\) 为奇数 的走法，则\(a' = a-c\)变为偶数。

并且由单调性仍满足 \(a'<b'\)，于是根据归纳假设，这个新状态对下一手是必败局面。因此先手可以一步把对手送入必败局面，所以当前局面必胜。

归纳完成，结论得证。

因此，在 \(a<b\) 的区域里，赢当且仅当 \(a\) 奇数且 \(\gcd(a,b)=1\)，此外整体计数可用对称性处理：\((a,b)\) 与 \((b,a)\) 同时输赢一致（交换两堆不改变规则），并且唯一在对角线 \(a=b\) 上满足 \(\gcd(a,b)=1\) 的是 \((1,1)\)。

令\(F(N)=\#\{(a,b): 1\le a<b,a+b\le N,a\equiv 1\pmod 2,\gcd(a,b)=1\}.\)则\(H(N)=1+2F(N).\)

定义\(F(N)\)的不要求互素的计数为：\(Q(N)=\#\{(a,b): 1\le a<b,a+b\le N,a\equiv 1\pmod 2\}.\)固定奇数 \(a\)，由于 \(a<b\) 且 \(a+b\le N\)，可得\(b\in\{a+1,\dots,N-a\},\)个数为 \(N-2a\)（当且仅当 \(2a<N\)）。

因此有\(\displaystyle{Q(N)=\sum_{\substack{a\equiv 1\pmod2 \\1\le a< N/2}} (N-2a)= \left\lfloor\frac{N^2}{8}\right\rfloor.}\)

对 \(Q(N)\) 中任意一对 \((a,b)\)，设\(g=\gcd(a,b).\)由于 \(a\) 是奇数，\(g\) 也只能是奇数。写成 \(a=gx, b=gy\) 且 \(\gcd(x,y)=1\)，则：\(x<y, x+y\le \left\lfloor\dfrac{N}{g}\right\rfloor, x\equiv 1\pmod 2.\)这正是 \(F(\lfloor N/g\rfloor)\) 的定义，因此所有 \((a,b)\) 按 \(g\) 分类后：\(\displaystyle{Q(N)=\sum_{\substack{g\ge 1\\g\equiv 1\pmod 2}} F\left(\left\lfloor\frac{N}{g}\right\rfloor\right).}\)

把 \(g=1\) 项移到左边，就得到核心递推：

\[ F(N)=Q(N)-\sum_{\substack{g\ge 1\\g\equiv 1\pmod 2}} F\left(\left\lfloor\frac{N}{g}\right\rfloor\right). \]

并且 \(F(1)=F(2)=0\)。

那么这题我们就可以使用数论分块来解决。设\(z=\lfloor\sqrt N\rfloor.\)把求和拆为两段：

  • \(g\le z\)：这些项数量只有 \(O(\sqrt N)\)：\(\displaystyle{\sum_{\substack{3\le g\le z\\g\equiv 1\pmod 2}} F(\lfloor N/g\rfloor)}\)，那么这些值可以直接枚举。
  • \(g > z\)：此时 \(\lfloor N/g\rfloor\) 只会取到 \(1,\dots,\lfloor N/(z+1)\rfloor\) 这些较小的值，并且同一商会覆盖一整段 \(g\)。令\(x=\left\lfloor\dfrac{N}{g}\right\rfloor,\)则对应的 \(g\) 区间为\(\left(\left\lfloor\dfrac{N}{x+1}\right\rfloor,\left\lfloor\dfrac{N}{x}\right\rfloor\right].\)该区间内奇数 \(g\) 的个数是：\(\left\lfloor\dfrac{r+1}{2}\right\rfloor-\left\lfloor\dfrac{l+1}{2}\right\rfloor.\)这样就能把大的 \(g\) 求和压缩成 \(O(\sqrt N)\) 项的加权和。

整体复杂度约为 \(O(N^{3/4})\)，内存约 \(O(\sqrt N)\)，足以处理 \(N=10^9\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from tools import int_sqrt
from functools import cache

N = 10 ** 9

def Q(n: int) -> int:
    return (n * n) // 8

@cache
def F(n: int) -> int:
    if n < 3:
        return 0
    s = Q(n)
    z = int_sqrt(n)
    for g in range(3, z + 1, 2):
        s -= F(n // g)
    lim = n // (z + 1)
    for x in range(1, lim + 1):
        cnt = ((n // x + 1) // 2) - ((n // (x + 1) + 1) // 2)
        if cnt:
            s -= cnt * F(x)
    return s

def H(n: int) -> int:
    return 1 + 2 * F(n)

print(H(N))