共计 1493 个字符，预计需要花费 4 分钟才能阅读完成。
| 如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有 a、b、c 可能的组合? 大佬们有更优的算法吗？ |
网友回复：
注册 ： 你这个算法的时间复杂度应该是 O(nlogn) 嘛，应该能优化到 O(n)的 我的理解啊：已知：1、直角三角形 2、三边只和长度为 1000 求：每条边都为正整数的所有解 因为：直角三角形一条直角边长已知，且周长已知，那么另外两条边有且仅有唯一解 如：短直角边 a 长直角边 b 斜边 c 当 a = 1 时 b 方 + a 方 = c 方 b 方 +1=(1000-1-b)方 b 方 +1=(1000-1)方 – 2*（1000-1）*b + b 方 1=(1000-1)方 – 2*（1000-1）*b b=((1000-1)方 – 1) / (2*（1000-1) ) 等号右边都是已知量，这时候只要 b 是正整数即为解，并且如果 a!=b，一下就求出来两个解，这里 500/ 根号 2 必不可能是整数，所以不存在等腰直角三角形的情况 所以: 只需要遍历一遍就够了，时间复杂度为 O(n) 伪代码：循环 a 从 1 到 500/ 根号 2，每次循环自增 1 b = ((1000-a)方 – a 方) / (2*（1000-a) ) if (b 为正整数 且 b < 500) 输出 a, b, c = a, b, 1000-a-b 输出 a, b, c = b, a, 1000-a-b 大概就是这样，循环到 500/ 根号 2 是因为，如果是等腰直角三角形的话边长最多就是 500/ 根号 2，再大就没有意义了，之前遍历过这样的情况 没验证，可能有 bug 哈
251768938： 直接枚举平方数会不会要好些？(指先预处理一个平方数库; 把 a^2 当作 a1,b^2 当作 a2,c^2 当作 a3,a1 和 a2 从平方数中枚, 加起来看下是不是平方数, 不是或者 sqrt(a3)不等于 1000-a- b 就继续枚)
ShadowSaint： 别和我说什么算法，无脑用 for 循环穷举就行了
xieshang： 穷举法, 极限也就那样
gdtv： 虽然想不出更好的，但是一看你这个就压根没用到啥算法，建议读读数论
2CO3： 能跑就行，能出来结果就行
lsin： 哪有什么最优，能算出来就行
bugtrap： 算个 P 法，暴力强算
HOH： 感谢大佬，明天我来实现
注册： 试了下 9 楼大佬的，楼主的时间是 200x，论坛居然不让发代码 …
注册： a+b>c 令 c >b>a（之后把算出来所有的满足条件的 ab 值交换即可得到所有可能性），因此 c 的值在 334 到 499 之间。(1000-c)^2-2ab=c^2 所以 ab=5e5-c，如果 c 为偶数，a 和 b 也为偶数，c 为奇数，ab 一奇一偶。
lsin： 说错了，c 应该是 334～500。其实我想到一种解法，固定 c 的值以后，画一条长为 c 的线段，再画一个以线段两端点为焦点的椭圆，上面的点到焦点距离和为 1，再画一个以线段为直径的正圆。通过椭圆和正圆的交点就可以求出 a 和 b 的值。
VPS 小白白： 我用手机打字不方便，应该是（上面的点到焦点距离和为 1000-c），因为这是个解方程题目，应该对于满足范围的每个 c 都能求出解，但我们只需要自然数解，所以可以不用求精确解，比如牛顿下山法之类的，每个 c 的求解，复杂度在 O(logN)，加上 c 的范围大概是 O(NlogN)
VPS 小白白： 而且 NlogN 应该是最坏的情况，精度为 1 的话牛顿下山法收敛很快的（基础不是很记得牢了），总之这个方法对数学要求较高一些。
VPS 小白白： 啊这。直接 abc 随便取一个变量，0 到 1000 遍历。比如把 c 从 0 到 1000 遍历，那这不就是求解一元二次方程的根了吗，一次遍历就结束了啊
