在知道斜边的情况下高效计算所有毕达哥拉斯三元组

Question

给定斜边（典型方程

c

中的

a*a + b*b = c*c

），计算

a

和

b

的所有可能整数值的有效方法是什么，使得

a < b

？

注意：我已经看到

c

大于

1e12

，因此

c*c

大于

long.MaxValue

，但据我所知，

c*c

确实适合

decimal

。

Answer 1

所有毕达哥拉斯三元组 (a,b,c) 满足以下性质：对于某些整数 k、m 和 n，

a=k(m^2-n^2), b=2kmn, c=k(m^2 + n^2)

所以从分解 c 开始。然后，对于 c 的每个不同的因子 k（即，对于每个不同的因子子集，相乘），找到满足 c/k = (m^2 + n^2) 的所有 m 和 n。执行后者将比其他人建议的暴力方法花费更少的时间（您只需找到总和为 c/k 的平方，而不是 c^2），但会识别所有三元组 (a,b,c) 。您也不需要使用 bignum，因为所有中间结果都适合 long。

我还建议您查看网页 http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Pythag/pythag.html 标题为“更通用的毕达哥拉斯三重计算器”其中包含一个用 javascript 编写的嵌入式计算器，它完全可以满足您的需求。

Answer 2

有一个数学解决方案，即使对于较大的

a

值，也可以快速找到

b

和

c

。

不幸的是，事情没那么简单。我试图对该算法进行简短的解释。我希望它不会太混乱。

由于给出了

c

并且您正在寻找

a

和

b

，您基本上想要求解以下形式的丢番图方程

n = x^2 + y^2

其中给出

n

。

n = c * c

是一个正方形并没有多大帮助，因此我正在描述任何

n

的解决方案。如果“n 是质数那么你可以使用 费马定理，确定您的方程是否可解，并使用 Moron 指出的 Hermite-Serret 算法来查找解（如果有）。

要解决

n

不是质数的情况，最好使用 高斯整数。 （高斯整数只是具有积分系数的复数）。特别值得注意的是 x + yi 的

norm

是

N(x + yi) = x^2 + y^2.

因此必须找到范数为

x + yi

的高斯整数

n

。

由于范数是乘法，因此足以求解该方程的因子

n

，然后乘以各个方程的高斯整数。

我举个例子。我们要解决

65 = x^2 + y^2.

这相当于找到

x

,

y

这样

N(x + yi) = 65

在高斯整数上。我们因式分解

65 = 5 * 13

，然后使用 Fermat 来注意到两者 5和13可以表示为两个平方和。最后，我们要么使用暴力破解，要么使用 Hermite-Serret 算法找到

N(2+i) = N(1+2i) = ... = 5
N(2+3i) = N(3+2i) = ... = 13

注意，我遗漏了高斯整数

2 - i

、

-2 + i

等，带有负系数。

这些当然也是解决方案。

因此我们现在可以将这些解决方案相乘得到

65 = 5 * 13 = N(2 + i) * N(2 + 3i) = N((2 + i) * (2 + 3i)) = N(1 + 8i)

和

65 = 5 * 13 = N(2 + i) * N(3 + 2i) = N((2 + i) * (3 + 2i)) = N(4 + 7i).

因此，得到两种解决方案

1 * 1 + 8 * 8 = 65
4 * 4 + 7 * 7 = 65

其他组合例如负系数也需要检查。

除了排列和改变符号之外，他们不会给出新的解决方案。

---

要计算所有解决方案，还可以补充一点，无需计算

c * c

。

找到

c

的因数就足够了。另外，由于 a 和

b

都小于

c

，因此不会出现高斯整数的乘积无法用 64 位整数系数表示的情况。因此，如果细心的话，64 位整数的精度足以解决这个问题。当然，使用像 Python 这样不存在此类溢出问题的语言总是更容易。

Answer 3

不妨选择 BigNum 库。

至于找到a和b的有效方法：

对于 b 的每个值（从 c-1 开始一直向下直到 b * b < c * c / 2), calculate c * c - b * b, and then check if it's a perfect square.

Answer 4

a 的值为 1，b 的值为 c。

将

c*c - b*b

与

a*a

进行比较。如果它们相等，则匹配。

根据较大的一侧将 a 和 b 相互改变，直到它们相同。

Answer 5

给定一个c：

由于 b > a，如果 a 最小 (a = 1)，则 b = sqrt(c*c - 1)。

因此 b 必须介于该值和 c -1 之间。

此外，由于 b 必须是整数，因此您需要找到第一个值为整数的值。

Now, a property of squares:
The squares are: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ...
The differences: -, 3, 5, 07, 09, 11, 13, 15, 17, 019, 021, ...
That means a square can be written as a summation of ODD numbers:
    1 + 3 + 5 + 7 + n+...
where n = number the summation is a square of.

因此正好有 c 个平方数小于 c*c，您可以使用简单的减法来识别它们。

回到开头，取b = sqrt(cc - 1)，向下取整并取bb，我们得到平方b一定在上面，并且aa = 1。找到cc - (a a + bb)。这将为您提供为实现 c*c 必须添加的数字。

由于您可以将

3 + 5 + 7 + ...

添加到 a，并将

b+2 + b+4 + b+6 + ...

添加到 b，因此您只需根据总和而不是平方本身找到正确的项即可:)