139. 毕达哥拉斯地砖(Pythagorean Tiles)

设 \((a, b, c)\) 表示一个边长均为整数的直角三角形的三条边。可以将四个这样的三角形拼在一起，形成一个边长为 \(c\) 的正方形。 例如，\((3, 4, 5)\) 三角形可以拼成一个 \(5 \times 5\) 的正方形，中间留有一个 \(1 \times 1\) 的孔，并且可以看到这个 \(5 \times 5\) 的正方形可以用二十五个 \(1 \times 1\) 的小正方形铺满。 然而，如果使用 \((5, 12, 13)\) 三角形，中间的孔将是 \(7 \times 7\)，这些孔无法用来铺满 \(13 \times 13\) 的正方形。 给定直角三角形的周长小于一亿，问有多少个毕达哥拉斯三角形满足这种铺砖条件？

分析：本题的核心是刻画哪些毕达哥拉斯三元组能够用中间的小方孔恰好铺满大正方形，即满足 \(|a-b| \mid c\)。通过数论推导可以证明，对于本原毕达哥拉斯三元组，该条件等价于 \(|a-b| = 1\)，而全体满足条件的三元组正是这些本原三元组的整数倍缩放。生成 \(|a-b| = 1\) 的本原三元组归结为求解佩尔方程 \(u^2 - 2v^2 = \pm 1\)，递推迭代即可。

一、数学背景

设 \((a, b, c)\) 为毕达哥拉斯三元组，满足 \(a^2 + b^2 = c^2\)。将四个同样的直角三角形拼成边长为 \(c\) 的正方形时（斜边构成外围），中间方孔的边长为 \(|a - b|\)。铺砖条件为 \(|a-b| \mid c\)（中间小方砖的边长整除大正方形的边长）。

核心定理：对于本原毕达哥拉斯三元组（\(\gcd(a,b)=1\)），\(|a-b| \mid c\) 当且仅当 \(|a-b| = 1\)。

证明：令 \(g = |a-b|\)，假设 \(g \mid c\)。设 \(c = gt\)，代入 \(a^2 + b^2 = c^2\)。不妨设 \(a = b + g\)（\(a, b\) 交换对称），则：

整理得：

由于 \(\gcd(b, g) = \gcd(b, a-b) = \gcd(b, a) = 1\)（本原三元组两直角边互质），且 \(\gcd(b+g, g) = \gcd(b, g) = 1\)，等式左边不含因子 \(g\)，因此 \(g^2 \mid 2\)，即 \(g = 1\)。\(\square\)

缩放不变性：对于任意整数倍 \((ka, kb, kc)\)（\(k \ge 1\)），条件 \(|ka-kb| \mid kc\) 等价于 \(k|a-b| \mid kc\)，约去 \(k\) 得 \(|a-b| \mid c\)。因此缩放不改变条件是否成立，只需关注本原三元组。

佩尔方程刻画：使用欧几里得参数化 \(a = m^2 - n^2\), \(b = 2mn\), \(c = m^2 + n^2\)（\(\gcd(m,n)=1\)，\(m, n\) 奇偶相异，\(m > n\)）。则：

令 \(u = m - n\), \(v = n\)，则 \(|a-b| = |u^2 - 2v^2|\)。条件 \(|a-b| = 1\) 等价于：

这正是经典佩尔方程，其全体正整数解由递推关系生成：

对应的本原三元组参数为 \(m = u + v\), \(n = v\)，周长为：

二、算法设计

1. 从佩尔方程的初始解 \((u, v) = (1, 1)\) 开始递推。
2. 对每一步，计算对应本原三元组的周长 \(p = 2(u + v)(u + 2v)\)，若 \(p \ge 10^8\) 则停止。
3. 对本原三元组的每个缩放倍率 \(k\)，三元组 \((ka, kb, kc)\) 的周长为 \(kp\)。需满足 \(kp < 10^8\)，即 \(k \le \lfloor (10^8 - 1) / p \rfloor\)，累加入总数。
4. 继续递推直至 \(p \ge 10^8\)。

三、复杂度分析

• 佩尔方程解的数量随步数指数增长，使得周长迅速超过上限。从 \((1,1)\) 出发仅需约 10 次递推。
• 每次递推为 \(O(1)\) 的整数运算，总时间复杂度 \(O(\log N)\)（\(N = 10^8\)）。
• 空间复杂度 \(O(1)\)，仅需维护 \((u, v)\) 和累加变量。

四、代码实现与说明

"""Project Euler 139 - Pythagorean Tiles
Count the number of right triangles with integer side lengths and perimeter < 10^8
for which exactly the large square of side length c can be tiled with central hole squares.
"""

def solve(limit: int = 100_000_000) -> int:
    """Count Pythagorean triangles with perimeter < limit satisfying the tiling condition.

    The tiling condition is that |a-b| divides c. For primitive Pythagorean triples,
    this holds iff |a-b| = 1. All scaled versions of such triples also satisfy it.

    Primitive triples with |a-b| = 1 correspond to solutions of u^2 - 2v^2 = ±1,
    generated via the Pell recurrence (u, v) -> (u + 2v, u + v).
    """
    total = 0
    u, v = 1, 1  # fundamental solution to u^2 - 2v^2 = -1

    while True:
        # perimeter p = 2 * (u+v) * (u+2v)
        perimeter = 2 * (u + v) * (u + 2 * v)
        if perimeter >= limit:
            break
        # k ranges from 1 to floor((limit-1) / perimeter) for scaled triples
        total += (limit - 1) // perimeter
        # next Pell solution
        u, v = u + 2 * v, u + v

    return total


if __name__ == '__main__':
    print(solve())

函数 solve

• 函数接收 limit 参数（默认一亿），返回满足条件的毕达哥拉斯三元组的个数
• total = 0：累加满足条件的三元组总数
• u, v = 1, 1：佩尔方程 \(u^2 - 2v^2 = -1\) 的基本解，对应本原三元组 \((3,4,5)\)

递推循环

• perimeter = 2 * (u + v) * (u + 2 * v)：计算当前本原三元组的周长 \(p = 2m(m+n) = 2(u+v)(u+2v)\)
• if perimeter >= limit: break：若本原三元组周长已达上限，后续更大，停止迭代
• total += (limit - 1) // perimeter：整数除法计算缩放倍率 \(k\) 的个数（\(1 \le k \le \lfloor 10^8-1 \rfloor / p\)），累加入总数
• u, v = u + 2 * v, u + v：佩尔方程 \(u^2 - 2v^2 = \pm 1\) 的递推公式，生成下一组解

主入口

• 调用 solve() 并输出结果