7

给定斜边（c在典型方程中），计算和a*a + b*b = c*c的所有可能整数值的有效方法是什么？aba < b

注意：我已经看到cbe 大于1e12，因此c*c大于long.MaxValue，据我所知，c*c确实适合 a decimal。

4

5 回答 5

7

所有毕达哥拉斯三元组 (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) . 您也不需要使用 bignums，因为所有中间结果都适合 long。

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

于 2010-01-28T04:46:12.533 回答
6

即使对于较大的 c 值，也有一个数学解决方案可以快速找到 a 和 b。不幸的是，事情并没有那么简单。我试图对算法做一个简短的解释。我希望它不会太混乱。

由于给出了 c 并且您正在寻找 a 和 b，因此您基本上想要求解以下形式的丢番图方程

n=x^2+y^2,

其中 n 是给定的。n = c*c 是一个正方形并没有多大帮助，因此我正在描述任何 n 的解决方案。如果 n 是素数，那么您可以使用 费马定理来确定您的方程是否可解，并使用 Moron 指出的 Hermite-Serret 算法来找到解决方案（如果有）。

要解决 n 不是素数的情况，最好使用 高斯整数。（高斯整数只是具有整数系数的复数）。特别是注意到x+yi的范数是

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

因此，必须找到范数为 n 的高斯整数 x+yi。由于范数是乘法的，因此对 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 这样没有这种溢出问题的语言总是更容易。

于 2010-01-28T09:39:57.600 回答
0

还不如去一个 BigNum 库。

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

对于 b 的每个值（从 c-1 开始直到 b * b < c * c / 2），计算 c * c - b * b，然后检查它是否是一个完美的正方形。

于 2010-01-28T01:17:29.910 回答
0

从 a 的值 1 和 b 的值 c 开始。

比较。c*c - b*b_ a*a如果他们是平等的，你有一个匹配。

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

于 2010-01-28T01:24:28.593 回答
0

给定交流：

由于 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(c c - 1)，四舍五入取 b b，我们得到平方 b 必须在上面，并且 a a = 1。找到 c c - (a a + b b)。这应该为您提供实现 c*c 必须添加的数字。

由于您可以添加3 + 5 + 7 + ...到 a 和b+2 + b+4 + b+6 + ...b，您只需要根据总和而不是平方本身找到正确的项 :)

于 2010-01-28T02:09:48.853 回答