142. 完全平方数集合(Perfect Square Collection)

求使得\(x + y + z\)最小的正整数\(x > y > z > 0\)，其中\(x + y\)、\(x - y\)、\(x + z\)、\(x - z\)、\(y + z\)、\(y - z\)六个表达式全部为完全平方数（即某整数的平方）。

一、数学背景

设六个完全平方数分别为：

$$ \begin{aligned} x + y &= a^2 & x - y &= b^2 \\ x + z &= c^2 & x - z &= d^2 \\ y + z &= e^2 & y - z &= f^2 \end{aligned} $$

由这些关系可以推导出\(x, y, z\)用\(a, b, c, d, e, f\)的表达式：

从\((x, y)\)的关系：

$$ 2x = a^2 + b^2, \quad 2y = a^2 - b^2 $$

从\((x, z)\)的关系：

$$ 2x = c^2 + d^2, \quad 2z = c^2 - d^2 $$

从\((y, z)\)的关系：

$$ 2y = e^2 + f^2, \quad 2z = e^2 - f^2 $$

由此得到三个核心等式：

$$ \begin{aligned} a^2 - b^2 &= e^2 + f^2 \quad (= 2y) \\ c^2 - d^2 &= e^2 - f^2 \quad (= 2z) \\ a^2 + b^2 &= c^2 + d^2 \quad (= 2x) \end{aligned} $$

所有六个平方数\(a^2, b^2, c^2, d^2, e^2, f^2\)必须满足相同的奇偶性约束（\(a\)与\(b\)同奇偶、\(c\)与\(d\)同奇偶、\(e\)与\(f\)同奇偶），以保证\(x, y, z\)为整数。

目标函数：

$$ x + y + z = a^2 + z = a^2 + \frac{e^2 - f^2}{2} $$

二、算法设计

采用枚举\(e, f\)的策略：

步骤1：枚举\((e, f)\)。 \(e\)和\(f\)必须同奇偶，且\(e > f > 0\)。对于每一对\((e, f)\)计算：

$$ y = \frac{e^2 + f^2}{2}, \quad z = \frac{e^2 - f^2}{2} $$

步骤2：从\(y\)求\((a, b)\)。 由\(2y = a^2 - b^2 = (a-b)(a+b)\)，令\(u = a-b, v = a+b\)，则\(u \cdot v = 2y\)。枚举\(2y\)的所有因子对\((u, v)\)，满足\(u < v\)且\(u, v\)同奇偶（保证\(a, b\)为整数）：

$$ a = \frac{u+v}{2}, \quad b = \frac{v-u}{2} $$

步骤3：验证\((c, d)\)。 由前面的推导：

$$ c^2 = a^2 - y + z, \quad d^2 = a^2 - y - z $$

检查\(c^2\)和\(d^2\)是否均为完全平方数，且\(c > d\)。

步骤4：返回最小和。 按\(e\)递增的顺序搜索，第一个满足所有条件的解即对应最小的\(x + y + z\)（因为\(x + y + z = a^2 + z\)，而\(a^2\)主要由\(e\)的大小决定）。

三、复杂度分析

四、代码实现与说明

#!/usr/bin/env python3
"""
Project Euler Problem 142: Perfect Square Collection
"""

import math
import time


def is_square(n):
    """Check if n is a perfect square."""
    if n < 0:
        return False
    r = int(math.isqrt(n))
    return r * r == n

is_square函数

def solve():
    e = 2
    while True:
        # e and f must have same parity for y,z to be integers
        for f in range(e % 2 + 2, e, 2):
            y = (e * e + f * f) // 2
            z = (e * e - f * f) // 2

            if z <= 0:
                break

            # Given y, find a such that a^2 - b^2 = 2y
            # 2y = (a-b)(a+b) = u * v where u < v, u*v = 2y
            two_y = 2 * y

            # Find factors of 2y
            u = 1
            while u * u <= two_y:
                if two_y % u == 0:
                    v = two_y // u
                    # a = (u+v)/2, b = (v-u)/2 must be integers and b > 0
                    if (u + v) % 2 == 0:
                        a = (u + v) // 2
                        b = (v - u) // 2
                        if b > 0:
                            # Now check c^2 and d^2
                            c2 = a * a - y + z
                            d2 = a * a - y - z

                            if c2 > 0 and is_square(c2) and d2 > 0 and is_square(d2):
                                c = int(math.isqrt(c2))
                                d = int(math.isqrt(d2))
                                x = (a * a + b * b) // 2
                                # Verify all conditions
                                if x > y > z > 0:
                                    if (a > b and c > d and e > f and
                                        a > c and c > e and e > b):
                                        return x + y + z
                u += 1
        e += 1

solve函数——外层循环

solve函数——因子分解与(a,b)求解

solve函数——验证(c,d)条件

def main():
    start = time.time()
    answer = solve()
    elapsed = time.time() - start

    print(f"Answer: {answer}")
    print(f"Time: {elapsed:.3f}s")


if __name__ == "__main__":
    main()

main函数

 

本站所有文章如非特别声明皆为原创，转载请与作者本人联系并注明出处(原文链接)。 如对文章有任何疑问或需指出错误，可以此页面提出问题，我会尽量及时回复。

←返回主页