知道hypoteneuse有效地计算所有毕达哥拉斯三元组
给定一个hypoteneuse（典型方程中a*a + b*b = c*c c a*a + b*b = c*c ），计算a和b所有可能整数值的有效方法是什么，这样a < b ？
注意：我看到c大于1e12 ，因此c*c大于long.MaxValue ，据我所知， c*c确实适合decimal 。
有一种数学解决方案即使对于较大的c值也能快速找到a和b。 不幸的是，事情并非那么简单。 我试图给出一个简短的算法解释。 我希望它不会太混乱。
由于给出了c并且你正在寻找a和b，你基本上想要求解forms的丢番图方程
n=x^2+y^2,
其中n给出。 n = c * c是一个正方形并没有多大帮助，因此我正在描述任何n的解。 如果n是素数，那么你可以使用费马定理 ，来决定你的方程是否可解，并使用，因为莫伦指出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，然后我们使用费马注意5和13都可以表示为两个正方形的总和。 最后，我们通过使用Hermite-Serret算法使用蛮力找到
N(2+i) = N(1+2i) = ... = 5 N(2+3i) = N(3+2i) = ... = 13
注意，我用负系数省略了Gaussion整数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这样没有这种溢出问题的语言总是更容易。
所有毕达哥拉斯三元组（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，因为所有中间结果都适合长。
我还建议您查看网页http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Pythag/pythag.html标题下的“更通用的毕达哥拉斯三重计算器”，其中包含嵌入式计算器，用javascript编写，完全符合你的要求。
不妨去BigNum图书馆。
至于找到a和b的有效方法：
对于b的每个值（从c-1开始并向下直到b * b
对于a，值为1，对于b，值为c。
将c*c - b*b与a*a 。 如果它们相等，那么你就是匹配。
根据哪一侧更大，将a和b朝向彼此改变，直到它们相同为止。
给定ac：
由于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 = 1.找到c c – （a a + b b）。 这应该为您提供必须添加的数字才能达到c * c。
既然你可以添加3 + 5 + 7 + ...到a，而b+2 + b+4 + b+6 + ...到b，你只需要根据总和找到合适的术语而不是广场本身:)